LeetCode: Single Number

This problem is quite similar the concept in digital circuit. First let us take a look at the code:

public int singleNumber(int[] A) { if(A.length==0) { return 0; } int ones=0, twos=0, threes=0; for (int i=0;i<A.length;i++){ twos |= ones & A[i]; ones = ones ^ A[i]; threes = ones & twos; ones = ones & ~threes; twos = twos & ~threes; } return ones; }

The variable twos and ones represent the number of 1 mod by 3 in the corresponding position ; for example, we have

A:0001,0111,0111,0111 In the for loop:

1. twos = 0000, ones = 0001, threes = 0000, ~threes = 1111, ones = 0001, twos = 0000 2. twos = 0001, ones = 0110, threes = 0000, ~threes = 1111, ones = 0110, twos = 0001 3. twos = 0111, ones = 0001, threes = 0001, ~threes = 1110, ones = 0000, twos = 0110

After three numbers, the number of digit 1 in four positions is 0, 2, 2, 3. In this case the ~threes will serve as a mask to reset the counter ones and twos