#136 Single Number
the problem
In plain words
Every number in nums appears exactly twice except one, which appears once. Find that one using linear time and constant extra space.
in nums = [2,2,1]
out 1
in nums = [4,1,2,1,2]
out 4
4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4.
in nums = [1]
out 1
- 1 ≤ nums.length ≤ 3·10⁴
- −3·10⁴ ≤ nums[i] ≤ 3·10⁴
- Every element appears twice except one
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternXOR cancellation
a ^ a = 0 and a ^ 0 = a, and order doesn't matter. XOR everything: every pair cancels and the single number is left.
solutions
From brute force to optimal
For each number, count how often it appears; return the one with count 1.
- For each candidate, scan the whole array and count matches.
- Return the candidate whose count is 1.
A full scan for each of the n candidates.
Only a counter.
class Solution { public int singleNumber(int[] nums) { for (int candidate : nums) { int count = 0; for (int num : nums) if (num == candidate) count++; if (count == 1) return candidate; } return -1; // problem guarantees an answer }}Add on first sight, remove on second; the survivor is the answer.
- For each num: if
addfails, it was there, so remove it. - The set ends with one element.
One pass with O(1) average set operations.
Up to n/2 unpaired values can wait in the set at once.
class Solution { public int singleNumber(int[] nums) { Set<Integer> seen = new HashSet<>(); for (int num : nums) { if (!seen.add(num)) seen.remove(num); // second sighting cancels the first } return seen.iterator().next(); }}XOR all numbers together; pairs cancel to 0.
- x = 0.
- For each num: x ^= num.
- Return x.
One pass, one XOR per element.
A single int accumulator.
class Solution { public int singleNumber(int[] nums) { int x = 0; for (int num : nums) { x ^= num; // pairs cancel: a ^ a = 0 } return x; }}Dry run
in the room
How to say it in the interview
talk track
- Give the HashSet answer first (O(n) space), then say: "The constant-space requirement hints at XOR."
- State the three XOR facts (
a^a = 0,a^0 = a, order-independent) before you write the loop. - Note that negatives work too, because XOR acts on the raw two's-complement bits.
traps
- Starting the accumulator at something other than 0.
- Sorting first. That works, but it is O(n log n), and the problem asks for linear time.
what they ask next
Follow-ups
Every other number appears three times (LC 137)?
XOR no longer cancels. Count each bit position mod 3 instead (see Single Number II).
Two numbers appear once (LC 260)?
XOR gives a ^ b. Split all numbers by one bit where a and b differ, then XOR each group (see Single Number III).
before you submit
Edge cases to test
- One element → that element.
- The single number is negative or 0: XOR works on the raw bits, so nothing changes.
- 20,000+ numbers: counting each value is O(n²) and too slow; XOR is one pass.
practise next
Similar problems
- #137Single Number IIMediumin Bits
- #260Single Number IIIMediumin Bits
- #268Missing NumberEasyin Bits