Problem

Given a non-empty array where every element appears twice except for one, find that single one. Solve with O(1) space.

Example

Input:  [2,2,1]
Output: 1

Input:  [4,1,2,1,2]
Output: 4

Solution

XOR all elements. Pairs cancel out (a XOR a = 0), leaving only the unique number.

def single_number(nums):
    result = 0
    for n in nums:
        result ^= n
    return result

function singleNumber(nums) {
    let result = 0;
    for (const n of nums) result ^= n;
    return result;
}

int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int n : nums) result ^= n;
    return result;
}

public int singleNumber(int[] nums) {
    int result = 0;
    for (int n : nums) result ^= n;
    return result;
}

Complexity

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

Explanation

XOR has two key properties: a XOR a = 0, and 0 XOR x = x. So XORing everything cancels out the duplicates and leaves the single value.