For a small input, the number of candies is small (up to 15). The search for all possible cases will consist of 2 ^ 15 = 32768 possibilities that can be checked within a millisecond or so. But with up to 1000 candies (high input), the number of possible combinations is 2 ^ 1000 = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376 . Now this number is too large, and even if you run the program for several years, you will not get the result.
There are a few notes that help in creating an effective program for this:
- As @Protostome points out, the amount Patrick sums up is actually an xor operation.
- Again, as @Protostome pointed out, if it is solvable, the xor of all candies will be 0. The reason is that if you can get the same amount of xor in two sections, then taking xor of both sections will be
a xor a = 0 . - If it is possible to split, then the sum xor of all candies is 0. But if we remove one candy from the set of whole candies, it will become non-zero. In particular,
.
c1 xor c2 xor ... xor ci-1 xor ci xor ci+1 xor ... xor cn = 0 => c1 xor c2 xor ... xor ci-1 xor ci+1 xor ... xor cn = ci
That is, we can split the set into two by pulling one candy from the whole set. To maximize the arithmetic sum of the left half, we must take the candy with the smallest value. So, the arithmetic sum of sweets in the highest heap is the sum of all sweets - the value of the lowest!
Therefore, we have:
- If xor of all candies is equal to zero, it is solvable
- If it is solvable, the sum is the sum of the entire list - the smallest value.