Single Number

Problem in plain words

Every value in the array appears exactly twice, except one value that appears only once. Return that lonely value, using linear time and only constant extra memory.

For example, in [8, 3, 8] the answer is 3.

Intuition

XOR has three properties that solve this instantly: x ^ x = 0, x ^ 0 = x, and it is commutative and associative, so the order of the elements does not matter. XOR the whole array together and every duplicate pair cancels itself out, leaving only the single value. A hash set would also work, but it needs O(n) memory, which the problem forbids. More XOR tricks are in the bitwise operations lesson.

Approach

1. Start with result = 0.
2. For every number x in the array, set result ^= x.
3. Return result.

Dry run

Input: [4, 7, 4, 2, 7].

The answer is 2. The intermediate values look random, but the pairs of 4 and 7 cancel by the end.

Java solution

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int x : nums) {
            result ^= x;   // pairs cancel, the single value remains
        }
        return result;
    }
}

Python solution

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for x in nums:
            result ^= x   # pairs cancel, the single value remains
        return result

Complexity

Edge cases and common mistakes

• Negative numbers: XOR works on the two's-complement bits, so negatives cancel just like positives.
• Array of one element: the loop returns that element.
• Sorting first: sorting and scanning pairs works but costs O(n log n) time.
• Using sum tricks: 2 * sum(set(nums)) - sum(nums) is correct but needs O(n) extra space for the set.