Given an array of integers where some numbers repeat 1 time or 2 times but one number repeats 3 times, how do you find it?

Question

Given an array of integers where some numbers repeat 1 time, some numbers repeat 2 times and only one number repeats 3 times, how do you find the number that repeat 3 times. Using hash was not allowed. Complexity of algorithm should be O(n)

Answer 1

I assume the array is not sorted, or similary, repeats of a number don't appear in one contiguous run. Otherwise, the problem is really trivial: just scan the array once with a window of size 3, and if each number in that window is the same, then that's the number that repeats 3 times in one contiguous run.

If the repeats are scattered, then the problem becomes more interesting.

Since this is homework, I will only give you a hint.

This problem is a cousin of where you're given an array of unsorted integers, and all numbers appear an even number of times, except one that appears an odd number of times.

That number can be found quite easily in O(N) by performing an exclusive-or of all the numbers in the array; the result is the number that appears an odd number of times.

The reason why this works is that x xor x = 0.

So for example, 3 xor 4 xor 7 xor 0 xor 4 xor 0 xor 3 = 7.