Single Number

Problem

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

Solution

First try of using Arrays.sort() solution

public class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i += 2) {
            if (nums[i] != nums[i+1]) return nums[i];
        }
        return nums[nums.length - 1];
    }
}

Optimal linear time solution using XOR

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

Analysis

I first thought about using sort, then compare every two pairs until we found difference
If we didn't find any difference, then the last number must be the single one
However, using XOR is faster (linear time) and safer (sort() might not be allowed to use in interview)
XOR return 1 only on different bits, if two numbers are equal, it returns 0
Therefore, since every other two numbers are equal, their XOR result must be 0 at the end
Then the final XOR result is the single we need to find
Bit manipulation is amazing ;)