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?
------------------------- read codes-----------------------------------------Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
if the question is four times
class Solution{
public:
int singleNumber(int A[], int n){
int oneNum = 0;
int twoNum = 0;
int threeNum = 0;
int fourNum = 0;
for(int i = 0 ; i < n ;i++){
fourNum = threeNum & A[i];
threeNum = twoNum & A[i] | threeNum;
twoNum = oneNum & A[i] | twoNum;
oneNum = oneNum | A[i];
oneNum = oneNum &(~fourNum);
twoNum = twoNum & (~fourNum);
threeNum = threeNum & (~fourNum);
}
return oneNum;
}
};
------------------------ thinking-------------------------------------------
public int singleNumber(int[] A) { int ones = 0, twos = 0; for(int i = 0; i < A.length; i++){ ones = (ones ^ A[i]) & ~twos; twos = (twos ^ A[i]) & ~ones; } return ones; }
The code seems tricky and hard to understand at first glance. However, if you consider the problem in Boolean algebra form, everything becomes clear.
What we need to do is to store the number of '1's of every bit. Since each of the 32 bits follow the same rules, we just need to consider 1 bit. We know a number appears 3 times at most, so we need 2 bits to store that. Now we have 4 state, 00, 01, 10 and 11, but we only need 3 of them.
In this solution, 00, 01 and 10 are chosen. Let 'ones' represents the first bit, 'twos' represents the second bit. Then we need to set rules for 'ones' and 'twos' so that they act as we hopes. The complete loop is 00->10->01->00(0->1->2->3/0).
- For 'ones', we can get 'ones = ones ^ A[i]; if (twos == 1) then ones = 0', that can be tansformed to 'ones = (ones ^ A[i]) & ~twos'.
- Similarly, for 'twos', we can get 'twos = twos ^ A[i]; if (ones* == 1) then twos = 0' and 'twos = (twos ^ A[i]) & ~ones'. Notice that 'ones*' is the value of 'ones' after calculation, that is why twos is calculated later.
Here is another example. If a number appears 5 times at most, we can write a program using the same method. Now we need 3 bits and the loop is 000->100->010->110->001. The code looks like this:
int singleNumber(int A[], int n) {
int na = 0, nb = 0, nc = 0;
for(int i = 0; i < n; i++){
nb = nb ^ (A[i] & na);
na = (na ^ A[i]) & ~nc;
nc = nc ^ (A[i] & ~na & ~nb);
}
return na & ~nb & ~nc;
}
Or even like this:
int singleNumber(int A[], int n) {
int twos = 0xffffffff, threes = 0xffffffff, ones = 0;
for(int i = 0; i < n; i++){
threes = threes ^ (A[i] & twos);
twos = (twos ^ A[i]) & ~ones;
ones = ones ^ (A[i] & ~twos & ~threes);
}
return ones;
}
I hope all these above can help you have a better understand of this problem.
----------------------------------------------------------------------------------------------------------------------
/*
we can think of this prolem is a ternary plus, if we do ternary plus for each bit of the number,
the 3 times number will reach 0, and only one number is not 0.
we can think of xor operation as no-carry binary plus, i.e., 0 ^ 1 = 0 + 1, 1^1 = 1+1 = 0 .
we can use (xor, and ,or) to implemnt quaternary plus, 0b10 + 0b01 = 0b11
and we can also use quaternary plus to implement ternary plus, by convert 0b11 to 0b00 after each plus.
*/
class Solution {
public:
int singleNumber(int A[], int n) {
//a is the second bit, b is first bit, a = 0, b= 1 denote 0b01, c is the current number in array.
int a= 0, b = 0, c = 0;
for (int i = 0; i < n; i++)
{
c = A[i];
//begin quaternary plus.
a = a ^ (b & c);// only b = 1 c = 1 can let a+=1.
b = b ^ c;// b+=1.
//end quaternary plus and begin convert 0b11 to 0b00.
c = a & b;// use c as temp variable to record a & b, we change 0b11 to 0b00
a = a & ~c;// make a = 0 if a ==1 and b == 1.
b = b & ~c;//make b = 0 if a == 1 and b == 1
//end converting 0b11
}
// the a and b is the result of ternary plus of the number we fould.
return a | b;
}
};
----------------------------------------------------------------------------------------------------------------------
class Solution{
public:
int singleNumber(int A[], int n){
int oneNum = 0;
int twoNum = 0;
int threeNum = 0;
for(int i = 0 ; i < n ;i++){
threeNum = twoNum & A[i];
twoNum = oneNum & A[i] | twoNum;
oneNum = oneNum | A[i];
oneNum = oneNum &(~threeNum);
twoNum = twoNum & (~threeNum);
threeNum = 0;
}
return oneNum;
}
};
easy to understand this solution
----------
oneNum means A[i] contains one bit 1
towNum means A[i] contains two bit 1
threeNum means A[i] contains three bit 1
if three bit 1 occurs than flip oneNum to 0 and twoNum to 0 and threeNum to 0
so the step will be like this
bit in oneNum will change like this 0-1-1-0
bit in twoNum will change like this 0-0-1-0
bit int threeNum will change like this 0 -1-0
and it is easy to expand to other situations like four same num and so on
--------------------------------------------------------------------------------------------------------------------------
Image the numbers in A have just one bit,
that is: A = [0, 0, 0, 1, 1, 1, x]
We have three times "0", three times "1", and a different "x".
So, if count of "1" in A is three's multiple, than x = 0,
else, x = 1.
Iterate all numbers in A.
When encount FIRST "1", set "ec1 = 1";
When encount SECOND "1", set "ec2 = 1";
When encount THIRD "1", set "ec3 = 1, ec1 = 0, ec2 = 0", and move on...
At last "ec1" is the different number.
class Solution:
# @param A, a list of integer
# @return an integer
def singleNumber(self, A):
ec1, ec2, ec3 = 0, 0, 0
for ai in A:
ec3 = ec2 & ai
ec2 = (ec2 | (ec1 & ai)) & (~ec3)
ec1 = (ec1 | ai) & (~ec3)
return ec1
If A contains six '1's, then x = 0.
If elements in A are just '0' or '1', and every element appears three times except
for one single element, then we can count the '1's in A to find the single element.
If count of '1's equals 3*n, then the single element is '0'.
If count of '1's equals 3*n+1, then the single element is '1'.
----------------------------------------------------------------------------------------------------------------------
class Solution {
public:
int singleNumber(int arr[], int n) {
// Initialize result
int result = 0;
int x, sum;
// Iterate through every bit
for (int i = 0; i < 32; i++)
{
// Find sum of set bits at ith position in all
// array elements
sum = 0;
x = (1 << i);
for (int j=0; j< n; j++ )
{
if (arr[j] & x)
sum++;
}
// The bits with sum not multiple of 3, are the
// bits of element with single occurrence.
if (sum % 3)
result |= x;
}
return result;
}
};
No comments:
Post a Comment