Leetcode: Single Number

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?

Understand the Problem:

As described in the problem, given an array of integers, every element appears twice except for one. The problem asks for finding the single one. Furthermore, the problem asks for linear time complexity and constant space complexity. 

Naive Approach:

As is described in the problem, each element appears twice except for one. So a straight-forward solution could use a hash set. For the element first encountered, we add it into the set. For the second met, we remove it. As a result, after iterating all elements of the array, the hashset only contains one element, which is the one we are looking for.

Code (Java):

public class Solution {
    public int singleNumber(int[] A) {
        HashSet<Integer> hashset = new HashSet<Integer>();
        int ret = 0;
        int len = A.length;
        
        for (int i = 0; i < len; i++) {
            if (!hashset.contains(A[i])) {
                hashset.add(A[i]);
            } else {
                hashset.remove(A[i]);
            }
        }
        
        for (Integer num : hashset) {
            ret = num;
        }
        return ret;
    }
}

Discussion:
As we can see that this approach has time complexity of O(n). However, the space complexity is O(n) as well since we used additional space. 

A better approach:
Since we are required to use constant space, we can think of using bit manipulation. We use XOR. Since x ^ x = 0. x ^ y ^ x = y. So we can use the XOR to eliminate the repeated numbers. 

Code (Java):

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

Discussion:
Note that the solution utilized two properties: First of all, XOR is comm.communicative, i.e. x ^ y ^ x = x ^ x ^ y = y. Second, The solution relied on the assumption that each number appeared two times while one appears once. If this condition does not stand, the solution of using XOR does not hold.

Summary:
This post we learned a very simple problem but required tricky solution to solve it. Using bit manipulation is very subtle. If you are asked to perform an operation without using extra space, consider the bit manipulation.