Description
Every integer in a non-empty array appears twice except one that appears once. Find that unique value using constant extra space.
Solution
def single_number(nums):
result = 0
for value in nums:
result ^= value
return resultExamples
Example 1
- Input
[[2,2,1]]- Output
1
The two 2s cancel.
Example 2
- Input
[[4,1,2,1,2]]- Output
4
Both repeated pairs cancel.
Example 3
- Input
[[-7]]- Output
-7
The only value is unique.
Approach
XOR every value. Equal values cancel because a XOR a is zero, and zero XOR a is a. XOR order does not matter.
Time & space
O(n) time and O(1) auxiliary space, where n is element count.