Problem overview
The method singleNumber receives a non-empty array of integers, nums. Every value appears exactly twice, except for one value that appears once. The method returns that single value.
For nums = [4, 1, 2, 1, 2] the 1s and the 2s come in pairs, and 4 is alone, so the answer is 4. For [2, 2, 1] the answer is 1, and for [1] the answer is 1 because the array holds only the single value.
The statement asks for O(n) time and O(1) extra space.
Approach: let equal numbers cancel out
The obvious solutions each break one of the two limits. Sorting the array and comparing neighbours costs O(n log n) time. Counting occurrences in a Map or a Set is O(n) time but needs O(n) extra space. This lesson uses a different property of numbers.
The bitwise XOR operator, ^, compares two numbers bit by bit and gives a 1 where the bits differ. It has three properties that matter here:
x ^ xis 0: a number cancels itself out.x ^ 0isx: XOR with 0 changes nothing.- The order doesn't matter: XOR is commutative and associative, so the numbers can be combined in any order.
Combine all the elements with XOR and each pair of equal values meets somewhere in the chain and turns into 0. Only the single value is left, combined with zeros. For [4, 1, 2, 1, 2], regroup the chain as 4 ^ (1 ^ 1) ^ (2 ^ 2), which is 4 ^ 0 ^ 0, which is 4. The pairs don't have to be next to each other in the array for this to work.
Step by step
- Declare
swithletand start it at 0. It holds the XOR of everything seen so far. Zero is the right start because0 ^ xisx, so the first element goes in unchanged. It is a single variable, which is why the extra space is constant. - Loop over
numswithfor...of, naming the elementvalwithconst. The loop never reassignsval, and each pass gets a fresh binding, soconstis fine. - Inside the loop, reassign
stos ^ val. After each pass,sis the XOR of the elements visited so far. - After the loop, return
s. Every duplicated value has cancelled, sosis the single number.
The solution in JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
singleNumber(nums) {
let s = 0
for (const val of nums) {
s = s ^ val;
}
return s
}
}A few details about JavaScript:
- Numbers are doubles, but
^works on 32-bit integers. The operator converts both operands to signed 32-bit integers, applies XOR and returns a normal number. The constraints keep every value between -30,000 and 30,000, far inside that range, so nothing is lost. - Negative values work.
-4 ^ -4is 0, and the array[-4, 7, -4]gives 7. The sign needs no special case because negative integers are stored in two's complement, and XOR treats their bits like any others. s = s ^ valcan be writtens ^= val. The two do the same thing.- The result can be negative. If the single value is -3, the method returns -3.
Complexity
The loop visits each element once and does a constant amount of work, so the time is O(n). The method keeps one variable, s, regardless of the array's length, so the extra space is O(1).
Edge cases and common mistakes
- A one-element array. The loop runs once,
0 ^ xisx, and the method returns the element. - Starting
sat something other than 0. Starting at 1, for example, would leave a stray 1 in the result. The starting value must be the identity of XOR. - Using
+or-instead of^. Sums don't cancel pairs in this way: adding[2, 2, 1]gives 5, not 1. - Relying on the pairs being adjacent. The solution doesn't need it.
[3, 5, 3, 5, 9]and[9, 3, 5, 3, 5]both give 9. - Expecting it to work for other counts. The cancelling trick depends on every other value appearing an even number of times. If a value could appear three times, one copy would survive and the result would be wrong.
Testing
Try these in the editor above:
[2, 2, 1]returns 1.[4, 1, 2, 1, 2]returns 4.[1]returns 1.[-4, 7, -4]returns 7.
