by hemangsarkar, Aug 25, 2015, 5:56 AM
Q) You are given an array of
numbers where every number appears
times except a particular number
which appears exactly once. Find that number
.
solutionThis is a coding problem and pretty well knows as such.
You can have nested "for loops" and check inside the second one if the number appears again. Here is the idea coded in C :
The array is a[n].
for(i=0;i<=n-1;i++)
{flag=1;
for(j=0;j<=n-1,j!=i;j++)
{
if(a
==a[j])
flag=0;
}
if(flag==1)
{
printf("%d is the number",![$a[i]$](//latex.artofproblemsolving.com/3/a/f/3af201e059def60855a46ca1e399e051b42a0534.png)
);
break;
}
}
There are two nested for loops and so the time complexity of the idea is 
.
We can actually do better by using BIT WISE XOR.
c = a xor b
a b c
0 0 0
0 1 1
1 0 1
1 1 0
If we have two numbers say 
and 
, the "BIT WISE" XOR is (001).
If a number is xored with itself, the resultant is 0.
The cool thing about this is that the it is associative in nature.
So if we XOR all the numbers of the array, the answer must be that one number that appears exactly once.
The rest appear twice each and so cancel out among themselves.
In C/C++ a^b means the bitwise XOR of a and b.
xor=0;
for(i=0;i<=n-1;i++)
{ ![$m = a[i]$](//latex.artofproblemsolving.com/7/6/f/76f356b9386fd6ae1519e3d5e3abadcf3be1107b.png)
;
xor = xor^m;}
printf("%d is the number",xor);
The time complexity is 
since we do just one traversal.
We can do better than this using divide and conquer idea.
This post has been edited 2 times. Last edited by hemangsarkar, Aug 25, 2015, 6:00 AM
numbers where every number appears 
times except a particular number 
which appears exactly once. Find that number ![$a[i]$](http://latex.artofproblemsolving.com/3/a/f/3af201e059def60855a46ca1e399e051b42a0534.png)
)
.
and 
,![$m = a[i]$](http://latex.artofproblemsolving.com/7/6/f/76f356b9386fd6ae1519e3d5e3abadcf3be1107b.png)
;
since we do just one traversal.
November 2016
June 2016