algorithm - Find the most common entry in an array

Question

You are given a 32-bit unsigned integer array with length up to 2³², with the property that more than half of the entries in the array are equal to N, for some 32-bit unsigned integer N. Find N looking at each number in the array only once and using at most 2 kB of memory.

Your solution must be deterministic, and guaranteed to find N.

Answer 1

Keep one integer for each bit, and increment this collection appropriately for each integer in the array.

At the end, some of the bits will have a count higher than half the length of the array - those bits determine N. Of course, the count will be higher than the number of times N occurred, but that doesn't matter. The important thing is that any bit which isn't part of N cannot occur more than half the times (because N has over half the entries) and any bit which is part of N must occur more than half the times (because it will occur every time N occurs, and any extras).

(No code at the moment - about to lose net access. Hopefully the above is clear enough though.)