Single Number
You get a list nums in which every value appears exactly twice, except for one value that appears only once. Return the value that appears once.
Function
- numsinteger-array
- a list where every value appears twice except one
- Returnsinteger
- the value that appears only once
Constraints
1 ≤ nums.length < 104-104 ≤ nums[i] ≤ 104- Every value appears exactly twice, except one value that appears exactly once.
Examples
- Input
- nums = [8, 3, 8]
- Output
- 3
- Explanation
- 8 appears twice and 3 appears once, so the answer is 3.
- Input
- nums = [5, -2, 7, 5, 7]
- Output
- -2
- Explanation
- 5 and 7 each appear twice, and -2 is the only value seen once. A negative answer is found the same way as a positive one.
- Input
- nums = [42]
- Output
- 42
- Explanation
- A list with one value has no pairs at all, so that value is the answer.
+13 hidden tests on Submit
Follow-up
What if every value appeared three times except one? XOR alone no longer cancels the triples. Can you still find the single value in O(n) time and O(1) extra memory?
Hints
Open them one at a time. Each one gives away a little more.
If every pair of equal values could be made to disappear, only the answer would be left. Is there an operation that turns two equal numbers into nothing?
XOR does:
x ^ xis0andx ^ 0isx. It is also order free, so the two copies of a value do not need to sit next to each other to cancel.Keep one variable that starts at
0. XOR every value ofnumsinto it, then return it. No map and no sorting are needed.
Solution
Finding the one value without a partner is a counting problem, and a hash map counts every value in one pass. The catch is memory: a map grows with the list. XOR removes the need to count at all, because XOR-ing a value with itself gives 0. XOR the whole list together and every pair erases itself, leaving the single value in one pass with one variable.
Count each value by scanning
Correct, but does not finish on the largest tests
Intuition
Take each value in turn and scan the whole list to count how many times it occurs. A value from a pair counts 2. The single value counts 1, so return the first value whose count is 1.
This is correct because the counts follow directly from the definition of the answer, and it needs no extra memory beyond a counter.
It is slow because each of the n values triggers a full scan of n values. When the single value sits at the end of a list of 9,999, that is close to 10^8 comparisons.
Algorithm
- Loop over each value in
nums. - Scan the whole list and count the values equal to it.
- If the count is 1, return that value.
def singleNumber(nums):
for value in nums:
# count() scans the whole list: O(n) per value.
if nums.count(value) == 1:
return value
return 0Count with a hash map
Intuition
Rescanning the list for every value repeats work. Count all the values in one pass instead: a hash map from value to count, where each step adds 1 to the count of the current value.
For [5, -2, 7, 5, 7] the map ends as 5 → 2, -2 → 1, 7 → 2. A second pass over the map finds the entry with count 1, which is -2.
Each value costs one map update, so the time is O(n). The map holds about n/2 entries, which is O(n) extra memory. In C, which has no built-in map, an array of counters indexed by value + 10^4 plays the same role because the values are small.
Algorithm
- Create an empty map from value to count.
- For each value in
nums, add 1 to its count. - Go through the map and return the value whose count is 1.
def singleNumber(nums):
counts = {}
for value in nums:
counts[value] = counts.get(value, 0) + 1
for value, count in counts.items():
if count == 1:
return value
return 0XOR all the values
Intuition
XOR compares two numbers bit by bit and sets a bit where they differ. Three facts follow: x ^ x = 0, x ^ 0 = x, and the order of the operations does not matter.
So XOR the whole list into one variable that starts at 0. You can regroup the operations so that each pair meets its twin, and every pair becomes 0. What remains is 0 ^ single, which is the single value. For [8, 3, 8]: 0 ^ 8 = 8, then 8 ^ 3 = 11, then 11 ^ 8 = 3.
Negative numbers work too. XOR acts on the bits of the two's complement form, and two equal negative numbers have equal bits, so they cancel like any other pair. The loop reads each value once and keeps one variable: O(n) time and O(1) extra memory.
Algorithm
- Set
resultto 0. - For each value in
nums, setresulttoresult ^ value. - Return
result.
def singleNumber(nums):
result = 0
for value in nums:
result ^= value
return result
Pitfalls and edge cases
The XOR loop is short, so the mistakes hide in where it starts and in the alternatives people reach for.
- Starting
resultatnums[0]and then looping over every value, index 0 included. The first value gets XOR-ed in twice and cancels itself. Start at 0, or skip index 0. - Sorting and comparing neighbors in steps of two, then forgetting that the single value can be the last element. In
[1, 1, 2]no mismatched pair exists, and the answer is the leftover 2. - Using
2 × sum(distinct values) - sum(nums). It gives the right number, but the set of distinct values costsO(n)memory, which the XOR version avoids. - Expecting XOR to work for other counts. It cancels values that appear an even number of times. If a value appeared three times, one copy would survive and spoil the answer.
Frequently asked questions4
What is the time complexity of Single Number?
The XOR solution runs in O(n) time and O(1) extra space, because it reads each value once and keeps one variable. A hash map also takes O(n) time but needs O(n) memory. Counting each value with a fresh scan takes O(n²).
Why does XOR solve Single Number?
XOR-ing a number with itself gives 0, XOR-ing with 0 changes nothing, and the order of the operations does not matter. So when you XOR the whole list, each pair can be grouped together and cancels to 0. Only the value without a partner is left.
Does the XOR trick work with negative numbers?
Yes. XOR works on the bits that store the number, and negative numbers are stored in two's complement. Two equal negative numbers have identical bits, so they cancel exactly like positive ones. In [5, -2, 7, 5, 7] the result is -2.
How do you solve it when the other values appear three times?
XOR cancels pairs, not triples, so it fails there. Instead, count how many values have each of the 32 bits set. For every bit, that count modulo 3 is the bit of the single value, because the triples add multiples of 3. This still runs in O(n) time with O(1) extra memory.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def singleNumber(nums):
# Write code hereCase 1
Case 2
Case 3
Input
nums = [8, 3, 8]
Expected
3