LeetCode Single Number II: Bit ADD Machine

LeetCode Single Number II Problem Description:

Given an array of integers, every element appears three times except for one. Find that single number.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

LeetCode Single Number II Solution and Precautions:

Of course, Sorting and Hashing could still work in exactly the same way as described in “leetcode: Single Number“.  The tricky part is how to tackle this problem by using bit operations and using constant memory.

Motivated by the thoughts in this “link“, I have come up with a different way by using bit operation to compress the memory usage and code up the solution from a different angle:

The basic idea is that, if we sum the i-th bit of all numbers and mod 3, it must be either ZERO or ONE due to the fact that each number must appear either three times or once in the single number problem description. And, this resulted bit is exactly the i-th bit of the single number we want. There is a straightforward approach by keeping 32 counters of the appearances of 1′s for each of the 32 bits and here I provide a bit compression version (yet another different one from the bit operation provided in that link) for that because essentially we only need to keep the counting mod by 3 instead of the exact countings, so only two bits are needed to keep this mod result, i.e., 0, 1, 2.  We sum the i-th bit of all numbers and use two integers Hi, Lo to keep the sum % 3. We use Hi[i] and Lo[i] to indicate the i-th bit. And we have the following, only three status for Hi[i], Lo[i] will appear, since 2 + 1 % 3 == 0.

Dec:   0  1  2
Hi[i]: 0  0  1 
Lo[i]: 0  1  0

In other words, we need to make a new “ADD Machine” as follows:

+0     |      +0      |      +0
         --->    |     --->     |     --->  
Hi[i]: 0      0  |   0      0   |  1       1
Lo[i]: 0      0  |   1      1   |  0       0

          +1     |      +1      |      +1
         --->    |     --->     |     --->  
Hi[i]: 0      0  |   0      1   |  1       0
Lo[i]: 0      1  |   1      0   |  0       0

After examining this machine and we can design the big operation like this:

newLo = (~Hi) & (Lo ^ A[i]);
    newHi = ( ~A[i] & (Hi ^ (Lo & A[i])) ) | ( A[i] & (~Hi & (Hi ^ (Lo & A[i]))) );

We can verify the correctness of the above formula by setting A[i] = 0 and A[i] = 1 respectively, and we can see, the newLo, newHi formula gives the same result of the “ADD Machine” we want! (Please try this by yourself as an exercise!) . The source code which can pass the leetcode OJ is as follows:

int singleNumber(int A[], int n) {
		int lo, hi, newlo, newhi, tmp;
		lo = hi = newlo = newhi = 0;
		for(int i = 0; i < n; ++i) {
			newlo = (~hi) & (lo ^ A[i]);
			tmp = (hi ^ (lo & A[i]));
			newhi = ( ~A[i] & tmp ) |
				    ( A[i] & (~hi & tmp) );
			lo = newlo;
			hi = newhi;
		}
		return newlo ^ newhi;
	}

LeetCode Single Number II Tips and Divergent thinking:

without using extra memory actually means using const memory. Don’t put too much attention on the “extra” part.

Written on January 17, 2014