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

Note: We generalize this problem to:

Given an array of integers, every element appears k times except for one which apprears l times. Find that single one whic appears l times.

Analysis:

The general solution is given in https://oj.leetcode.com/discuss/857/constant-space-solution

Now I try to explain the general solution.

First, we only consider one bit (either one in the bit sequence of each element in A). The idea is to record how many times 1 is appreaed for this bit. We use an array X with length k to indicate 0 - k-1 times. If 1 appreas j times, then X[j] is marked as 1. We scan the array A, and want to express such logic:

1. If A[i] on this bit is 0, then X array remains its original value.

2. If A[i] on this bit is 1, then

　　2.1 if 1 has appreared j-1 times, i.e., X[j-1]==1, then X[j] =1 now.

　　2.2 if 1 has appreared j times, i.e., X[j]==1, then X[j]=0 now.

　　2.3 if 1 has appreaed some other times, then X[j] remains the same, i.e., still 0.

We use logic table to express this logic:

Note that X[j-1]==1 && X[j]==1 will not happen.

Then we change the table to logic expression formula:

new X[j] = (~X[j-1] & X[j] & ~A[i]) | (X[j-1] & ~X[j] & A[i]).

Since X[j] & X[j-1] will not happen, it does not matter what output it will be, so we assume the output will be 1 to simply the expression, then we have:

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

NOTE: This is the formula used in the general solution, but we have not reached there. CONTINUE.

Since if 1 apprears k times, then it equals to apprear 0 times, we have X[0] = (old X[k-1] & A[i]) | (X[0] & ~A[i]).

Now, with this formula, we can count how many times the 1 has appreared on some specific bit position for array A. It also means that we can know that what the value that apprears l times on some specific bit position. It is the value of X[l]. NOTE, it is either 1 or 0.

Second, since there is no relationship between each bit in a number, we can directly use the above formula to operate the number, the answer then will be the value that apprears exactly l times on each bit, which is the ANSWER we want.

Solution:

NOTE: This solution is posted by Ronmocy in LeetCode.

 1 public class Solution { 2     public int singleNumber(int[] A, int k, int l) { 3         if (A == null) return 0; 4         int t; 5         int[] x = new int[k]; 6         x[0] = ~0; 7         for (int i = 0; i < A.length; i++) { 8             t = x[k-1]; 9             for (int j = k-1; j > 0; j--) {10                 x[j] = (x[j-1] & A[i]) | (x[j] & ~A[i]);11             }12             x[0] = (t & A[i]) | (x[0] & ~A[i]);13         }14         return x[l];15     }16 }

Leetcode- Single Number II