<p>You are given a 32-bit unsigned integer array with length up to 2<sup>32</sup>, 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.</p>

<p>Your solution must be deterministic, and guaranteed to find N.</p>

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.)