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.
- Input
- nums = [42]
- Output
- 42
- Explanation
- A list with one value has no pairs at all, so that value is the answer.
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
A hash map finds the value without a partner by counting, but the map grows with the list. XOR needs no counting, because a value XOR-ed with itself gives 0. XOR the whole list together and every pair erases itself, leaving the single value in one variable.
Count each value by scanning
Correct, but does not finish on the largest tests
Intuition
For each value, scan the whole list and count its copies; return the first value whose count is 1. The counts follow the definition of the answer, so the result is correct. Each of the n values triggers a scan of n values: close to 10^8 comparisons when the single value ends a list of 9,999.
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
Count every value in one pass with a hash map from value to count. For [5, -2, 7, 5, 7] the map ends as 5 → 2, -2 → 1, 7 → 2, and a pass over the map finds -2.
Each value costs one map update, so the time is O(n). The map holds about n/2 entries, O(n) extra memory. C has no built-in map, so an array of counters indexed by value + 10^4 plays its role.
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 sets a bit where its two inputs differ. So x ^ x = 0, x ^ 0 = x, and the order of the operations does not matter.
XOR the whole list into a variable that starts at 0. Regroup the operations so each value meets its twin: every pair becomes 0, and 0 ^ single leaves the single value. For [8, 3, 8]: 0 ^ 8 = 8, then 8 ^ 3 = 11, then 11 ^ 8 = 3. 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
- Starting
resultatnums[0]and then looping over every value, index 0 included. The first value is 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 last. In
[1, 1, 2]every pair checked matches, and the answer is the leftover 2. - Reusing the XOR loop when values can appear an odd number of times. It cancels only even counts, so in
[4, 4, 4, 9]it returns4 ^ 9 = 13, not 9.
Frequently asked questions3
What is the time complexity of Single Number?
The XOR solution runs in O(n) time and O(1) extra space. A hash map also takes O(n) time but needs O(n) memory. Counting each value with a fresh scan takes O(n²).
Does the XOR solution 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.
Can you solve Single Number with sums instead of XOR?
Yes. 2 × sum(distinct values) - sum(nums) is the single value: each paired value adds twice on both sides, the single value twice and once. For [5, -2, 7, 5, 7] that is 2 × 10 - 22 = -2. The set of distinct values costs O(n) memory, which XOR avoids.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def singleNumber(nums):
# Write code hereTest #1
Test #2
Test #3
Argument
nums = [8, 3, 8]
Expected Output
3