Single Number

Thanks Wei for suggesting this problem to me. This is a very tricky, but simple question. People may not think of the approach at first glance. Once it came to your mind, then remaining thing become much easier.

For XOR operation, one rule we need to know is: x^y=y^x. Order DOES NOT matter.

Check out my code below:

 public class Solution {  
   public int singleNumber(int[] A) {  
     if(A.length == 0) return 0;  
     int tmpRes = A[0];  
     for(int i = 1; i < A.length; i++){  
       tmpRes ^= A[i]; //x^y = y^x, so x ^ y ^ ~x ^ z ^ ~y = x ^ ~x ^ y ^ ~y ^ z = 0 ^ 0 ^ z = z  
     }  
     return tmpRes;  
   }  
 }  

And also thank Code_Ganker for his alternative solutions. Brilliant! His algorithm:

 public int singleNumber(int[] A) {  
   int[] digits = new int[32];  
   for(int i=0;i<32;i++)  
   {  
     for(int j=0;j<A.length;j++)  
     {  
       digits[i] += (A[j]>>i)&1;// get cumulative sum on each bit  
     }  
   }  
   int res = 0;  
   for(int i=0;i<32;i++)  
   {  
     res += (digits[i]%2)<<i;  
   }  
   return res;  
 }