algorithm - Find three numbers appeared only once

Question

In a sequence of length n, where n=2k+3, that is there are k unique numbers appeared twice and three numbers appeared only once.

The question is: how to find the three unique numbers that appeared only once?

for example, in sequence 1 1 2 6 3 6 5 7 7 the three unique numbers are 2 3 5.

Note: 3<=n<1e6 and the number will range from 1 to 2e9

Memory limits: 1000KB , this implies that we can't store the whole sequence.

Method I have tried(Memory limit exceed)：

I initialize a tree, and when read in one number I try to remove it from the tree, if the remove returns false(not found), I add it to the tree. Finally, the tree has the three numbers. It works, but is Memory limit exceed.

I know how to find one or two such number(s) using bit manipulation. So I wonder if

we can find three using the same method(or some method similar)?

Method to find one/two number(s) appeared only once:

If there is one number appeared only once, we can apply XOR to the sequence to find it.

If there are two, we can first apply XOR to the sequence, then separate the sequence into 2 parts by one bit of the result that is 1, and again apply XOR to the 2 parts, and we will find the answer.

Answer 1

For a more general version of this problem (without those silly limits):

You can do this in O(n) time and O(1) space without assuming any bounds, or iterating over all the bits, and using only O(1) time bit manipulation tricks like the XOR trick which worked for 2 missing numbers.

Here is (pseudo)code to find just one of the numbers:

// Given an array arr with 2k+3 numbers, k of which are repeated twice
// and the remaining three are distinct: a,b,c.
// returns one of a,b,c.
int FindUnique(int []arr) {

    int s = 0; // This will ultimately hold a ^ b ^ c (bitwise XOR)

    for (int i = 0; i < arr.Length; i++) {
        s ^= arr[i];
    }

    int d = 0; // this holds diff(a,s) ^ diff(b,s) ^ diff(c,s)

    for (int i = 0; i < arr.Length; i++) {
        d ^= diff(arr[i],s);
    }

    int e = lowestBit(d); // This gives the position where one of a,b,c differs 
                          // from the others.

    int bucket1 = 0;
    int bucket2 = 0;

    for (int i = 0; i < arr.Length; i++) {
        if (arr[i] & e) {
            bucket1 ^= arr[i];
        } else {
            bucket2 ^= arr[i];
        }
    }

    int count1 = 0;
    int count2 = 0;

    for (int i = 0; i < arr.Length; i++) {
        if (arr[i] == bucket1) {
            count1++;
        }

        if (arr[i] == bucket2) {
            count2++;
        }
    }

    if (count1 == 1) return bucket1;

    return bucket2;
}

// return a number with the lowest bit of x ^ s set to 1 and rest 0.
// i.e. the lowest bit position where x and s differ.
int diff(int x, int s) {
    return lowestBit(x ^ s);
}

// Returns a number with only the lowest bit of y set.
int lowestBit(int y) {
    return y & ~(y-1);
}

The idea is as follows:

Say the numbers which appear once are a,b,c.

Now run the XOR through the array to get s = a XOR b XOR c.

Since the numbers are distinct, notice that s cannot be either a or b or c (as the other two will be equal then), thus there is at least one bit (not necessarily at the same position), where each of a,b,c differs from s.

In the two number case, we could see that s is non-zero and pick a bit which differentiated a & b and work with that.

We run into difficulties with that when we have three numbers, but we can still find a bit to differentiate one of the numbers out.

For each number x, find the lowest bit which differs from s. Consider the binary number in which only that bit is set to one and the rest are zero. Call this number diff(x).

Now if we compute diff(x) for each number and XOR them together, we get d = diff(a) XOR diff(b) XOR diff(c).

Notice that d cannot be zero.

Now find the lowest set bit of d. This bit position can be used to bucket out one of a,b,c, as not all of a,b,c can have the same bit at that position: if they did, then that bit of s which is the XOR of those three must be the same, but we ensured that we picked that bit of s to differ from at least one of the corresponding bits in a,b,c.

So we XOR again, differentiating on this bit, and check which of the two resulting numbers appears exactly once in the array. Once we find one number, we know how to deal with two numbers.

To find the diff just use the bithack: x & ~(x-1), which is a standard bit-hack and can be considered O(1) (instead of O(number of bits)).