[Leetcode] Single Number

Problem

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

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

Algorithm

1. Hash Table

Use a hash table to record the occurrences of numbers. O(n) time and O(n) space. 

2. Count Ones Method

Let ones[] be an array counting the number of occurrence of 1s in each digit in the array. 

For example, A = [2,2],   ones = [2,0], 

                      A = [3,3,1], ones = [2,3]. 

If a number appeared twice, it will contribute 2X 1s in each digit. Therefore, by taking a mod of 2, we can eliminate the contribution from those numbers. The remaining of ones array is the binary representation of the single number. 

For example, A = [3,3,2,2,1], ones = [4,5], the single number is ones%2 = [0,1] = 1. 

If we use an array to store the ones array, we need O(n) space. 

3. Bit Manipulation

Note, y^0 = y, and x^x = 0.

Let the array A = [x1,x1, x2,x2, .... y], where x are numbers appeared twice and y is the number appeared once. Let res = 0 at first, apply the operation "^" with res and every number in the array. 

res = 0 ^x1 ^ x1 ^ x2 ^ x2 ^... ^ y

     = 0 ^ (x1 ^ x1) ^ (x2 ^ x2) ^ ... ^ y

     = 0 ^ 0 ^ 0 ^ ... ^ y

     = y

Note, The bit manipulation can also be understood in this way. 

Note 0^0 = 0, 0^1 = 1, 1^0 = 1, and 1^1 = 0, x^y = (x+y)%2. 

We used the res (O(1) space) to count the ones' occurrence. 

4. Triplet Manipulation

If other numbers appeared twice, we can use one integer res to count 1s, using the relation  

                                                                  (x+y)%2 = x^y,

Since each digit in the integer only has two states, 0 or 1. When other numbers appeared three times, a single bit is not enough to count number larger than 2.  We need to construct a Triplet, using two bits.

Let triplet [two, one] represent a number ranging from [0, 1, 2, 3]. 

For example,
                 [0,0] = 0, [0,1] = 1, [1,0] = 2, [1,1] = 3.
Some additions are 

                [0, 0] + 1 = [0, 1]//0 ^ 1 = 1

                [0, 1] + 1 = [1, 0]//carry to two

                [1, 0] + 1 = [1, 1]//one ^ 1

                [1, 1] + 1 = [0, 0]//clear by mask

So, the plus one to a triplet is equivalent to

twos = twos | (ones & A[i]);

ones = ones ^ A[i];

int mask = ~(ones & twos);

ones &= mask;

twos &= mask;

5. Single Number where other numbers appeared N times. 

Code