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

Question

I suppose the name might be a little misleading, but I couldn't think of a better one. I have an array A [], everything except one of the elements of which occurs a certain number of times, a multiple of 15, for example. 2 occurs 30 times, 3 - 45 times. But one element has x times, where x is not a multiple of 15. How to print the number x. I am looking for a linear solution without a hash table.

Thank.

Answer 1

Here was a similar question in StackOverflow, but I can not find it.

Let's use 3 instead of 15 because it will be easier and I think it is completely equivalent. The sequence will be 4, 5, 4, 5, 3, 3, 4, 5in binary format 100, 101, 100, 101, 11, 11, 100, 101.

: 3 (15 ):

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

!= 0, 1 , . :

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

, bit3 == 0, bit2 != 0, bit1 != 0, 011. : 3.

O(1), O(n * BIT_LENGTH_OF_VARS), BIT_LENGTH_OF_VARS == 8 , BIT_LENGTH_OF_VARS == 32 int .. , , O(n * BIT_LENGTH_OF_VARS) O(n).

!