algorithm - Finding an element in an array that isn't repeated a multiple of three times?

Question

After reading this interesting question I was reminded of a tricky interview question I had once that I never satisfactorily answered:

You are given an array of n 32-bit unsigned integers where each element (except one) is repeated a multiple of three times. In O(n) time and using as little auxiliary space as possible, find the element of the array that does not appear a multiple of three times.

As an example, given this array:

1 1 2 2 2 3 3 3 3 3 3

We would output 1, while given the array

3 2 1 3 2 1 2 3 1 4 4 4 4

We would output 4.

This can easily be solved in O(n) time and O(n) space by using a hash table to count the frequencies of each element, though I strongly suspect that because the problem statement specifically mentioned that the array contains 32-bit unsigned integers that there is a much better solution (I'm guessing O(1) space).

Does anyone have any ideas on how to solve this?

Answer 1

It can be done in O(n) time and O(1) space.

Here is how you can do it with constant space in C#. I'm using the idea of "xor except with 3-state bits". For every set bit, the "xor" operation increments the corresponding 3-state value.

The final output will be the number whose binary representation has 1s in places that are either 1 or 2 in the final value.

void Main() {
    Console.WriteLine (FindNonTriple(new uint[] 
                        {1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3} ));
    // 1

    Console.WriteLine (FindNonTriple(new uint[] 
                        {3, 2, 1, 3, 2, 1, 3, 2, 1, 4, 4, 4, 4} ));
    // 4
}

uint FindNonTriple(uint[] args) {
    byte[] occurred = new byte[32];

    foreach (uint val in args) {
        for (int i = 0; i < 32; i++) {
            occurred[i] = (byte)((occurred[i] + (val >> i & 1)) % 3);
        }
    }

    uint result = 0;
    for (int i = 0; i < 32; i++) {
        if (occurred[i] != 0) result |= 1u << i;
    }
    return result;
}