PWC 211 #2 Geared toward the average rather than the exceptional
Tags: perl, perlweeklychallenge, pwc
Published: 2023-04-09 22:49:42

Task 2 of the [Perl Weekly Challenge](https://theweeklychallenge.org/blog/perl-weekly-challenge-211/#TASK2) is a problem that benefits from analysis before opening the editor.  The statement sounds easy:

> You are given an array of integers. Write a script to find
> out if the given array can be split into two separate arrays
> whose average are the same.

My mind immediately starts thinking about combinations of _n_ things taken _k_ at a time, the efficiency of calculating sums and averages. The factorials involved in that are going to blow up for anything bigger than the small lists given as examples, and there's potential nastiness in comparing floating point values, which these averages are likely to be.

## "Mr. Miller, are we ever going to use algebra in real life?"
So let's start with some math.  We have a list of length _N_.  Let's call the sum of the numbers in that list _S_.  Now we want to partition the list into two subsets; let's say they have sizes _Na_ and _Nb_, and the sum of each subset is _Sa_ and _Sb_.  Clearly _N_ = _Na_ + _Nb_ and _S_ = _Sa_ + _Sb_.

The condition we're aiming for is that both subsets have the same average: _Sa_/_Na_ = _Sb_/_Nb_.  Starting with that and substituting for _Sb_,
> Sa/Na = Sb/Nb
> Sa/Na = (S - Sa)/Nb
> Sa &times; Nb = (S - Sa) &times; Na = S&times;Na - Sa&times;Na
> Sa&times;Na + Sa&times;Nb = S&times;Na
> Sa&times;(Na + Nb) = S &times; Na
> Sa &times; N = S &times; Na
> Sa/Na = S/N

So, if there is any solution that makes _Sa_/_Na_ = _Sb_/_Nb_ true, then at least one of the solutions must be that each of the subsets has the same average as the overall average. We could similarly reach _Sb_/_Nb_ = _S_/_N_ if we start by substituting (_S_-_Sb_) for _Sa_. 

So what does this buy us?  First of all, it gives us an easy way to test for a solution:  if any subset has an average that's the same as _S_/_N_, we can stop. We don't even have to check the average of the complementary set.  If the first subset has sum _Sa_, count _Na_, and average _S_/_N_, then the other partition must also have average _S_/_N_:
> Sa/Na = S/N
> (S-Sb)/(N-Nb) = S/N
> N&times;(S-Sb) = S&times;(N-Nb)
> S&times;N - Sb&times;N = S&times;N - S&times;Nb
> Sb&times;N = S&times;Nb
> Sb/Nb = S/N

Furthermore, instead of having to find every possible subset, which would be 2<sup>N</sup> possibilities, we only have to look at subsets up to size `floor(N/2)`, which is a huge reduction in operation count.

There's another helpful thing that results from this. The average number that we're testing for is likely to be a floating point value.  We don't really want to test for equality of floating point numbers; the road to hell is paved with floating point comparisons.

Knowing that we are looking for _S_/_N_ = _Sa_/_Na_, it must be true that _Sa_ = (_S_&times;_Na_)/_N_; and since _Sa_ must be an integer (since all the terms in the sum are integers), it must be true that (_S_&times;_Na_)&nbsp;%&nbsp;_N_ = 0. We can quickly check for any size _Na_ whether that is even possible by looking at _S_&times;_Na_%_N_, and we can quickly calculate _Sa_ without iterating over the array by evaluating _S_&times;_Na_/_N_.

_Now_ we can start thinking about [code.](https://github.com/boblied/perlweeklychallenge-club/tree/master/challenge-211/bob-lied/perl/ch-2.pl)

-----
[*] The title comes from the 1972 album "Thick as a Brick", by Jethro Tull.  The album came with a fake newspaper attached, containing humorous fake articles that the music referenced. One of the articles was about education reform that would be "geared toward the average rather than the exceptional" so that it would "relieve the crushing burden of individual aspiration.”