Single Number XOR

Find the one integer that appears exactly once in a list where every other number appears twice.

xor bit-manipulation arrays

Write a function `single_number(nums)` that takes a non-empty list of integers `nums`. In the list, every integer appears exactly twice except for one integer that appears exactly once. Return that single integer.

Your solution must run in O(n) time and use O(1) extra space. The XOR operation is your best friend here, but you are free to solve it however you like as long as the constraints are met.

Constraints

- 1 <= len(nums) <= 10^5
- Each element is an integer in the range [-10^9, 10^9]
- Exactly one element appears once; all others appear exactly twice.
- Expected time complexity O(n), expected space complexity O(1).

Example

>>> single_number([2, 2, 1])
1
>>> single_number([4, 1, 2, 1, 2])
4
>>> single_number([7])
7
>>> single_number([-1, 0, -1])
0

10 points ~12 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about how XOR behaves when applied to a number with itself.

XOR is commutative and associative: the order of operations doesn't matter.

Try XORing all the numbers together and see what remains.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.