136. Single Number Leetcode Java

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Solution:

This solution is not a general solution for this kind of problem. Please refer next problem: 137. Single Number II for a general solution.

This solution use a special bit operator to distinguish the single number: the xor exclusive or(^) bit operator. Two main facts that used in this problem. 

1. x^x=0;

2. 0^x=x;

So if we use the exclusive or for each number in the array, we will find the single one. Because all elements appear twice will cancelled out to 0, and leave the single one ^ 0= single one.

Time complexity: O(n)

  public int singleNumber(int[] A) {  
    if(A==null || A.length==0) return 0;  
    int res=0;  
    for(int i=0;i<A.length;i++){  
      res=res^A[i];  
    }  
    return res;  
   }