Find the one number that appears once while all others appear twice
Given a non-empty array of integers where every element appears exactly twice except for one, return that single element. Requirements: O(n) time and O(1) extra space — a hash count of occurrences uses O(n) space and is the baseline to beat.
function singleNumber(nums) {
// your code here
}Write the implementation.
XOR every element together — nums.reduce((a, b) => a ^ b, 0). XOR is commutative and associative, x ^ x === 0, and x ^ 0 === x, so each pair cancels to zero and only the lone value survives. This is O(n) time and O(1) space, beating the hash-count baseline that needs O(n) memory.
- ✗Reaching for a hash map or
Setcount, which solves it but at O(n) space - ✗Forgetting that XOR's identity is
0, so the reduce must seed the accumulator with0 - ✗Assuming XOR only works on sorted input — order does not matter to it
- →How would the XOR approach change if every other element appeared three times?
- →Why does seeding
reducewith0rather thannums[0]keep the code correct?
Solution
XOR-ing every element cancels all pairs and leaves the lone value.
function singleNumber(nums) {
return nums.reduce((acc, n) => acc ^ n, 0);
}How it works
XOR has three properties: it is commutative and associative (order does not matter), x ^ x === 0 (equal values cancel), and x ^ 0 === x (0 is the identity). So XOR-ing the whole array turns every duplicate pair into 0, and the remaining single number survives.
There is exactly one pass — O(n) time — and one accumulator is stored — O(1) space. The hash-count baseline is also O(n) time but pays O(n) in memory.
