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

For this question, there should be several fairly simple naive approaches.

For example, for every element in the list, we compare it with all other elements in the list. If there is an element which does not have a “sibling”, then this element is the one which we should return.

However, the approach above is NOT efficient, it has a time complexity of O(n^2) since every element needs to compare to the whole array. When the array is large enough…… SLOW!

Now, the question is, how should we make it FASTER, is it possible to make it run in O(n)?

Let’s think about it. Two is always an interesting number. In order to make the algorithm finish in O(n) time. We probably need to find a way to make those two values “cancel out”.

Cancelling out two same values… Um… O(n)… OH!!!! What about BIT OPERATION!

0000 xor 1111 = 1111

1111 xor 1111 = 0000

That’s definitely what we want!

So, we define a variable “result”, then we just xor the first number with 0 and store it to “result” and xor every number after that with the previous “result” and store it back to “result”. After one traversal, guess what we get? We get that little poor lonely value!

Java:

public class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for(int i = 0; i < nums.length; i++){
            result ^= nums[i];
        }
        return result;
    }
}

That’s it!