Estimating frequency of element of an array in O(n) time

Question

I suppose the title might be a little misleading, but I couldn't think of a better one. I have an array A[], all but one of whose elements occurs some number of times that is a multiple of 15, e.g. 2 occurs 30 times, 3 occurs 45 times. But one element occurs x times where x is not a multiple of 15. How do I print the number x. I'm looking for a linear solution without a hash-table.

Thanks.

Answer 1

There was similar question here, on StackOverflow, but i can't find it.

Lets use 3 instead of 15, because it will be easier and i think that it is completely equivalent. The sequence will be 4, 5, 4, 5, 3, 3, 4, 5, in binary 100, 101, 100, 101, 11, 11, 100, 101.

You can do the following: sum all values in least significant bit of numbers and take remainder over 3 (15 originally):

bit1 = (0 + 1 + 0 + 1 + 1 + 1 + 0 + 1) % 3 = 5 % 3 = 2 != 0

if it is != 0 then that bit is equal to 1 in number that we are trying to find. Now lets move to the next:

bit2 = (0 + 0 + 0 + 0 + 1 + 1 + 0 + 0) % 3 = 2 % 3 = 2 != 0

bit3 = (1 + 1 + 1 + 1 + 0 + 0 + 1 + 1) % 3 = 6 % 3 = 0 == 0

So we have bit3 == 0, bit2 != 0, bit1 != 0, making 011. Convert to decimal: 3.

The space complexity is O(1) and time complexity is O(n * BIT_LENGTH_OF_VARS), where BIT_LENGTH_OF_VARS == 8 for byte, BIT_LENGTH_OF_VARS == 32 for int, etc. So it can be large, but constants don't affect asymptotic behavior and O(n * BIT_LENGTH_OF_VARS) is really O(n).

That's it!