• The recursion terminates when there is either 1 number in the final array (in which case, this is the candidate solution) or there are no numbers left in the final array (in which case there is no candidate).
• For the solution to work, it has to guarantee that if there is a candidate solution in the first array, then in the produced array it is still the candidate. I think that the easiest way to do this is to examine the left-over item and see if it is a candidate. If it is, then return it immediately, otherwise forget about it. This will not change the order of the running time, since you're only doing it for at most one element during each round.

  I think that there were a bunch of solutions given that don't quite work. Among them were simply copying the extra element down, and comparing the last element with the first. These should both break on this example. Try your method on it, and see how it works.

  The example: 3,3,3,2,2,2,2,2,2,2,3,3,3

• The proper recurrence here is T(n) = T(n/2) + O(n). If you solve this recurrence, it turns out that T(n) = O(n). To see this consider expanding this recurrence out: T(n) = O(n) + O(n/2) + O(n/4) + ... . This is always bounded above by O(2n) = O(n).

  Note: A simple sniff test can tell you that it can't work in O(log n) time, since we can't even look at all the elements in O(log n) time.

• We would like to not use more than O(1) extra storage, and if possible not completely destroy the original array. We can get away with using only one temp variable, and we need only rearrange, not delete, the values in the given array.

  We keep an index into the array that begins at the first element. As we progress down the pairs, if we find a matching pair, we swap that element with the element under our index and increment the index. After we've traversed the array, we then recurse on the portion of the array that lies before the index. In this way, we keep the "interesting" portion of the list at the front of the array, and never have to actually delete anything.

Solution by Isaac Kunen, 10.4.2000