## Single Number II

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?

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

### Analysis:

The general idea of this problem, is to consider all the numbers bit by bit, count the occurrence of '1' in each bit. To get the result, check if the number can be divided by 3 (mod 3 = 0), put '0' if true and '1' otherwise.**(Idea coming from the internet)**

Since we know that XOR operation can be used for testing if 1 bit occurs twice, in other words, for a single bit, if 1 occurs twice, it turns to 0.

Now we need a 3-time criteria for each bit, by utilizing the bit operations.

This 3-time criteria needs every bit turns to 0 if '1' occurs three times.

If we know on which bits '1' occurs twice, and also know on which bits '1' occurs 1-time, a simple '&' operation would result in the bit where '1' occurs three times. Then we turn these bit to zero, would do well for this problem.

(1). Check bits which have 1-time '1', use the XOR operation.

(2). Check bits which have 2-times '1's, use current 1-time result & current number.

(3). Check bits which have 3-times '1's, use '1-time' result & '2-times' result

(4). To turn 3-times bits into 0: ~(3-times result) & 1-time result

~(3-times result) & 2-times result

E.g.,We have numbers: 101101, 001100, 101010

To count the occurrence of 1's:

101101

001100

101010

count: {2,0,3,2,1,1}

Denote:

t1: bit=1 if current bit has 1-time '1'

t2: bit=1 if current bit has 2-times '1'

t3: bit=1 if current bit has 3-times '1'

Result:

t1 = 000011, t2 = 100100, t3 = 001000

Initialization: t1 = 000000, t2=000000, t3 = 000000

(1) 101101

t1 = 101101 (using XOR)

t2 = 000000

t3 = 000000

(2)001100

% Current 2 times bits (t2) and NEW 2 times bits coming from 1 time bits and new number.

t2 = t2 | 001100 & t1 = 001100 & 101101 = 001100

t1 = t1 XOR 001100 = 100001

t3 = t2 & t1 = 000000

(3)101010

t2 = t2 | (101010 & t1) = t2 | (101010 & 100001) = 101100

t1 = t1 XOR 101010 = 100001 XOR 101010 = 001011

t3 = t1 & t2 = 001000

%Turn 3-time bits into zeros

t1 = t1 & ~t3 = 000011

t2 = t2 & ~t3 = 100100

### Code(C++):

class Solution { public: int singleNumber(int A[], int n) { int t1 = 0; int t2 = 0; int t3 = 0; for (int i = 0; i < n; i++){ t1 = t1 ^ A[i]; t2 = t2 | ((t1^A[i]) & A[i]); t3 = ~(t1 & t2); t1 = t1 & t3; t2 = t2 & t3; } return t1; } };

### Code(Python):

class Solution: # @param A, a list of integer # @return an integer def singleNumber(self, A): t1 = 0; t2 = 0; t3 = 0; for a in A: t2 = t2 | (t1 & a); t1 = t1 ^ a; t3 = ~(t1 & t2); t1 = t1 & t3; t2 = t2 & t3; return t1;

Here is another solution:

ReplyDeletepublic class Solution {

public int singleNumber(int[] nums) {

int p = 0;

int q = 0;

for(int i = 0; i<nums.length; i++){

p = q & (p ^ nums[i]);

q = p | (q ^ nums[i]);

}

return q;

}

}

Analysis from http://traceformula.blogspot.com/2015/08/single-number-ii-how-to-come-up-with.html

Wanna briefly explain traceformula's code:

ReplyDeletep is the bits that appear twice

q is the bits that appear once or twice