CareerCup

I found an awesome Algo for the same on the Internet:

1. So as usual find the XOR of all the @n+2 numbers
2. Next find in th XOR result find any bit which has been set. Like say if XOR result is number '5' then we know that 0th bit (LSB) in 5 (0101) is set
3. Divide the array into two parts A and B. A will contain those elements in which that bit is set and B will contain those elements in which that bit is not set
4. Finally XOR all the elements of A and all the elements of B.
- Result of XOR on A gives us the first element and Result of XOR on B gives the second element

Use combination of XOR and (n*n-1)/2 operations.


int nValue=0;
int nMinusOneValue=0;
int n=arr.length-1;
int XOR = 0;

for(int i=0;i<=n;i++){

XOR = XOR ^ arr[i];
nValue=nValue+arr[i];

if(i < n){
nMinusOneValue=nMinusOneValue+arr[i];
}


}

int oneValue=Math.abs(nValue-nMinusOneValue);

int otherValue=oneValue ^ XOR;

Why not use Hashtable?

Why not use Hashtable?

Why not use Hashtable?