Single Number

easy bit manipulation xor

Problem

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Inputnums = [4, 2, 9, 4, 2]

Output9

4 ⊕ 2 ⊕ 9 ⊕ 4 ⊕ 2 = 9.

nums (every value paired except one)

def single_number(nums):
    acc = 0
    for x in nums:
        acc ^= x
    return acc

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

class Solution {
    public int singleNumber(int[] nums) {
        int acc = 0;
        for (int x : nums) acc ^= x;
        return acc;
    }
}

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

Explanation

Every value shows up twice except one. The elegant trick is to XOR everything together in a single accumulator and let the duplicates cancel themselves out.

XOR has two magic properties: x ^ x = 0 (a value cancels itself) and x ^ 0 = x (XOR with zero leaves a value unchanged). It is also order-independent, so we can combine the numbers in any sequence.

So as we fold every number into acc with acc ^= x, each paired value meets its twin somewhere and vanishes to zero. Only the unpaired value never gets cancelled, and it survives in acc.

We start acc at 0 and return it at the end — one pass, no extra memory.

Example: nums = [4, 2, 9, 4, 2]. Computing 4 ^ 2 ^ 9 ^ 4 ^ 2, the two 4s cancel and the two 2s cancel, leaving 9.

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