Single Number

bit-manipulationxor

Problem

Given a non-empty array of integers nums, every element appears TWICE except for one. Find that single one, using only O(1) extra space.

Examples

Example 1

Input: nums = [2,2,1]

Output: 1

Explanation: 2 appears twice, 1 appears once.

Example 2

Input: nums = [4,1,2,1,2]

Output: 4

Explanation: 1 and 2 each appear twice; 4 is the single element.

Constraints

•1 <= nums.length <= 3*10^4
•-3*10^7 <= nums[i] <= 3*10^7
•Every element appears twice except one

Hints

Hint 1

The brute force: count every number's frequency with a hash map, then report whichever has count 1 — O(n) time, but O(n) extra space.

Hint 2

The O(1)-space requirement is the real signal here — what operation, applied to every element, could cancel out anything appearing an even number of times?

Hint 3

XOR: a^a = 0 for any a, and XOR is order-independent — XORing the whole array cancels every pair, leaving only the unpaired element.

Solutions

public int singleNumberBruteForce(int[] nums) {
    Map<Integer, Integer> counts = new HashMap<>();
    for (int n : nums) counts.merge(n, 1, Integer::sum);
    for (var entry : counts.entrySet()) {
        if (entry.getValue() == 1) return entry.getKey();
    }
    throw new IllegalArgumentException("No single number found");
}

Time: O(n) · Space: O(n)