Single Number
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)