LeetCode: Single Number II

Problem:

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?

Analysis:

We can extend this question: Every element appears N times and only one appears M times (M < N). Using a state machine, this problem is simple and straightforward. In our case, N = 3 and M = 1. Focusing on each bit of the number, we have N=3 states. Initially, that bit is 0, we have the initial state (0, 0). Then we scan the array and check that bit for each scanned number. If that bit first becomes 1, we have the state ( 0, 1). Next time it is 1, we change the state (0, 1) -> (1,0). If that bit becomes 1 for the N=3 times, the state will be back to (0, 0). Here is an example:

Array = {1, 2, 1, 1}.

Since N=3, we have three states. We can put all states into a array S[N]. (S[0] is NOT used here.)

Scan the array:

1) scan 1 (00000001):
                     S[2]: 00000000

                 S[1]: 00000001

                  S[0]: 11111111 (NOT used here)

                                           ^

                 state (0, 1) for this bit. Observe the state vertically. 

2) scan 2 (00000010):        
                      S[2]: 00000000

                   S[1]: 00000011

                   S[0]: 11111111 (NOT used here)

                                       ^

                                 state (0, 1) for this bit 

                                       ^

                                 state (0, 1) for this bit  

3) scan 1 (00000001):       
                      S[2]: 00000001

                   S[1]: 00000010

                   S[0]: 11111111 (NOT used here)

                                     ^

                            state (1, 0) for this bit 

                                      ^

                          state (0, 1) for this bit  

3) scan 1 (00000001):        
                      S[2]: 00000000

                   S[1]: 00000010

                   S[0]: 11111111 (NOT used here)

                                       ^

                        state back to (0, 0) for this bit 

                                       ^

                           state (0, 1) for this bit 

Therefore, we can get the single number which is S[1] = 2. 

As you can see, after we scan all the elements in the array, only S[M] will be has some bits which are not 0 and S[M] is the result. This is because except for the result number, other numbers will make all the bits back to the initial state and the final left bits which are not 0 will from the result number. 

Ok, now we can summary the algorithm. Each time we scan a number A[i] from the array A, we will 

update each state S[j] in array S. The bit of S[j] will be 1 if that bit of S[j] is previously 1 and the 

corresponding bit of A[i] is 0, or the bit of S[j-1] is 1 but the corresponding bit of A[i] is 1. This can 

be expressed as: S[j] = (S[j]&~A[i])|(S[j-1]&A[i]). If j==0, we set j-1=N-1.

C++:

We use N=3 and M = 1 for this problem.

#define N=3

#define M=1

class Solution {

public:

    int singleNumber(int A[], int n) {

        int S[M]; int t;

        S[0] = ~0;   //S[0] is used for the computation only. You can think S[0] will record the number which only appear 0 time

        for(int i=1; i<M; i++)

            S[i] = 0;

        

        for(int i=0; i<n; i++){

            t = S[N-1];

            for(int j=N-1; j>0; j--){

                S[j] = (S[j-1]&A[i])|(S[j]&~A[i]);

            }

            S[0] = (t&A[i])|(S[0]&~S[i]);

        }

        

        return S[M];

    }

};

Cost:

O(n)

We can also think the problem in another way. By adding up all elements in the array, we then mod N for each bit. The result will be the solution. 

C++2:

#define N=3

#define M=1

class Solution {

public:

    int singleNumber(int A[], int n){

        int res=0;

        for(int i=0; i<sizeof(int)*8; i++){

            int count=0;

            for(int j=0; j<n; j++){

                if((A[j]>>i)&1!=0)

                    count++;

            }

            res|=((count%N)<<i);

        }

        return res;

    }

};

Cost:

O(n)