In an array where every element appears twice except for one, finding that unique element is a classic coding interview challenge. While you could use a hash map, bitwise XOR provides an O(1) space solution.
Problem Statement
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
Example
Input: nums = [4, 1, 2, 1, 2]
Output: 4
Explanation: All numbers appear twice except for 4.
The XOR Property
XOR (^) has specific properties that make it perfect for this:
- Self-Cancellation: x ^ x = 0. A number XORed with itself becomes zero.
- Identity: x ^ 0 = x. XORing any number with zero keeps the number unchanged.
- Commutative: Order doesn't matter (a ^ b ^ a is the same as a ^ a ^ b).
Python Implementation
def find_single_number(nums):
result = 0
for n in nums:
result ^= n
return result
# Test
print(find_single_number([4, 1, 2, 1, 2])) # Output: 4
Complexity
- Time Complexity: O(N) - We traverse the array once.
- Space Complexity: O(1) - We only use one variable to store the result.