124. Single Number

XOR of a number with itself is 0, and XOR with 0 leaves a number unchanged. XOR every element together: all the paired numbers cancel to 0 and only the unique element remains.

Idea

Exclusive-or (XOR, written ^) has three properties that make this problem collapse to a one-liner:

• x ^ x = 0 — a number XORed with itself is zero.
• x ^ 0 = x — XOR with zero changes nothing.
• XOR is commutative and associative — order doesn't matter.

So if we XOR every element together, each value that appears twice contributes x ^ x = 0, and those zeros don't affect the running result. The one element that appears once is XORed in a single time and survives.

Algorithm

1. result = 0.
2. For each num, do result ^= num.
3. Return result.

Worked example: [4,1,2,1,2]

XOR left to right (using bit patterns):

The two 1s cancel, the two 2s cancel, and 4 — the unique value — remains. Return 4.

Complexity

• Time: O(n) — a single pass.
• Space: O(1) — one accumulator, satisfying the constant-space requirement.

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