Question I've been given at the job interview. I was close to the solution but did not solve it unfortunately.
Assume we have a sequence that contains N numbers of type long. And we know for sure that among this sequence each number does occur exactly n times except for the one number that occurs exactly m times (0 < m < n). How do we find that number with O(N) operations and O(1) additional memory?
For the simplest case (when n = 2 and m = 1) all that we should do is just to perform accumulative xor on every number in sequence. The result will be equal to the desired number. But i'm stuck while trying to deal with arbitrary m and n.
I would appreciate an actual C++ solution.
EDIT: We know actual values of m and n a priori.
Example. We know that n = 3 and m = 2. The sequence (N = 8) is
5 11 5 2 11 5 2 11
And the right answer is 2 in this particular case because it occurs only twice.