Single Number
Solve this Problem
Somewhere in this array, exactly one value breaks the pattern — everything else shows up in a matching pair, but one number stands alone with no partner. Find it.
Order doesn't matter here, and there's no need to track which values you've already seen: XOR-ing every element together in a single pass cancels every paired value down to nothing (since
x ^ x = 0), leaving only the unpaired value behind.
Test Case 1:
Input:nums = [2, 2, 1]
Output:1
Explanation:2 shows up twice; 1 is the lone value.
Test Case 2:
Input:nums = [4, 1, 2, 1, 2]
Output:4
Explanation:1 and 2 each appear twice; 4 stands alone.
Test Case 3:
Input:nums = [1]
Output:1
Explanation:A single-element array — that one value is automatically the answer.
Constraints
- ◆
1 ≤ nums.length ≤ 3 × 10⁴ - ◆
-3 × 10⁴ ≤ nums[i] ≤ 3 × 10⁴ - ◆
Every value in nums appears exactly twice, except for one value which appears exactly once
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Hashmap Counting
GoodCount how many times each value occurs using a hashmap, then scan the map for the one entry whose count is 1. Correct and still linear time, but it needs extra memory proportional to how many distinct values are in the array.
Time
O(n)Space
O(n)Java
1class Solution {
2 public int singleNumber(int[] nums) {
3 Map<Integer, Integer> freq = new HashMap<>();
4 for (int num : nums) {
5 freq.put(num, freq.getOrDefault(num, 0) + 1);
6 }
7 for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
8 if (entry.getValue() == 1) {
9 return entry.getKey();
10 }
11 }
12 return -1;
13 }
14}Optimal — XOR All Elements
OptimalXOR has two properties that solve this directly: x ^ x = 0 (a value cancels itself out), and x ^ 0 = x (XOR with nothing changes nothing), and it doesn't matter what order the values arrive in. XOR every element together in a single pass — every paired value cancels itself out, and whatever remains is the one value with no partner to cancel against.
Time
O(n)Space
O(1)Java
1class Solution {
2 public int singleNumber(int[] nums) {
3 int result = 0;
4 for (int num : nums) {
5 result ^= num;
6 }
7 return result;
8 }
9}