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?

Example :

Input : [1 2 2 3 1]
Output : 3

Method:

a ^ a = 0, we can keep XOR the numbers, the final result is the single number.

Solution:

Time: O(n)
Space: O(1)

public class Solution {
    // DO NOT MODIFY THE LIST. IT IS READ ONLY
    public int singleNumber(final List<Integer> A) {
        int single = 0;
        for (int i : A) {
            single = single ^ i;
        }
        return single;
    }
}

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