Expected time complexity is O(n) and O(1) extra space.
Examples:
Input: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}
Output: 2
We know that
when we XOR same number twice, we can get 0.
XOR operation is associative, commutative.It does not matter in what fashion elements appear in array, we still get the answer.
Method 1)
So in order to get One element which appears once,
We need to take care of two variable.
Once, Twice and Thrice.
Algo :
1) Whenever we get element, XOR’d to the variable “ones”.
2) Now if its repeated number it will be removed from “ones” and we xor it to “twice”.
3) A number appears twice will be removed from once, twice and stored in “thrice”
4) To remove all those are in common to “ones” and “twice” What we do is…
not_threes = ~(ones & twos)
ones & = not_threes
twos & = not_threes
= > Now as we want to store twice appearing number as well, we need to perform them first so that before it gets 0 in ones, we store it.
Sample Code
for( i=0; i< 10; i++ )
{
x = B[i];
twos |= ones & x ;
ones ^= x ;
not_threes = ~(ones & twos) ;
ones &= not_threes ;
twos &= not_threes ;
}
printf(“n unique element = %d n“, ones );
return 0;
Lets Trace values for input {12, 1, 12,1, 1, 12, 2}
-
Iteration =0 step = 1,two=0 Iteration =0 step = 2 ,ones=12 Iteration =0 step = 3 ,not_threes=-1 Iteration =0 step = 4 ,ones=12 Iteration =0 step = 5 ,twos=0
-
Iteration =1 step = 1,two=0 Iteration =1 step = 2 ,ones=13 Iteration =1 step = 3 ,not_threes=-1 Iteration =1 step = 4 ,ones=13 Iteration =1 step = 5 ,twos=0
-
Iteration =2 step = 1,two=12 Iteration =2 step = 2 ,ones=1 Iteration =2 step = 3 ,not_threes=-1 Iteration =2 step = 4 ,ones=1 Iteration =2 step = 5 ,twos=12
-
Iteration =3 step = 1,two=13 Iteration =3 step = 2 ,ones=0 Iteration =3 step = 3 ,not_threes=-1 Iteration =3 step = 4 ,ones=0 Iteration =3 step = 5 ,twos=13
-
Iteration =4 step = 1,two=13 Iteration =4 step = 2 ,ones=1 Iteration =4 step = 3 ,not_threes=-2 Iteration =4 step = 4 ,ones=0 Iteration =4 step = 5 ,twos=12
-
Iteration =5 step = 1,two=12 Iteration =5 step = 2 ,ones=12 Iteration =5 step = 3 ,not_threes=-13 Iteration =5 step = 4 ,ones=0 Iteration =5 step = 5 ,twos=0
-
Iteration =6 step = 1,two=0 Iteration =6 step = 2 ,ones=2 Iteration =6 step = 3 ,not_threes=-1 Iteration =6 step = 4 ,ones=2 Iteration =6 step = 5 ,twos=0 Finally unique element = 2
Method 2)
Check that input
{12, 1, 12, 1, 1, 12, 2} and its binary
{1100, 0001, 1100, 0001, 0001, 1100, 0010}
Sum of Unit digit = 0+1+0+1+1+0+0 = 3 % 3 = 0
Sum of Decimal digit = 0+0+0+0+0+0+1 = 1%3 =1
so
BitWise OR of ALL VALUES where Sum%3 != 0 is answer.
#define INT_SIZE 8
int getSingle(int arr[], int n)
{
int result = 0;
int x, sum,i,j;
for (i = 0; i < INT_SIZE; i++)
{
sum = 0;
x = (1 << i);
for (j=0; j< n; j++ )
{
if (arr[j] & x)
sum++;
}
if (sum % 3){
result |= x;
printf(“X=%dn”,x);
}
}
return result;
}
int main()
{
int arr[] = {12, 1, 12, 1, 1, 12, 3};
int n = sizeof(arr) / sizeof(arr[0]);
printf(“The element with single occurrence is %d “,
getSingle(arr, n));
return 0;
}
Output
X=1
X=2
The element with single occurrence is 3