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 lone value.
In the example [4, 1, 2, 1, 2], the values 1 and 2 each appear twice and 4 appears once, so the answer is 4. With [2, 2, 1] the answer is 1, and with the one-element array [1] the answer is 1.
The lesson asks for O(n) time and O(1) extra space. That rules out sorting, which costs O(n log n), and counting with a HashMap or HashSet, which uses O(n) memory.
Approach: let equal numbers cancel out with XOR
The bitwise XOR operator, written ^ in Java, compares two numbers bit by bit and gives a 1 where the bits differ and a 0 where they match. Two properties solve this problem:
x ^ x == 0: a number XORed with itself cancels to zero.x ^ 0 == x: XOR with zero leaves a number unchanged.
XOR is also commutative and associative, so the order of the operations doesn't matter. XOR all the elements together, and the two copies of every duplicated value cancel each other out, wherever they sit in the array. What remains is the lone value.
For [4, 1, 2, 1, 2], the running XOR starts at 0 and goes 0 ^ 4 = 4, then 4 ^ 1 = 5, then 5 ^ 2 = 7, then 7 ^ 1 = 6, and finally 6 ^ 2 = 4. The same result comes from regrouping: 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4.
Step by step
- Declare an accumulator
sas anintset to 0. Zero is the starting value because XOR with 0 changes nothing, so the first element goes in unchanged. - Loop over
numswith a for-each loop. Each element is read once and the array is not modified, so a for-each loop fits. - Fold each value into
sby assignings = s ^ val. Pairs cancel as they meet, and the single value stays. - Return
s. After the loop it holds the number that appeared once.
The solution in Java
class Solution {
public int singleNumber(int[] nums) {
int s = 0;
for (int val: nums) {
s = s ^ val;
}
return s;
}
}
Java details worth a closer look:
^is XOR, not a power. Java has no exponent operator. Between twointvalues,^always works on bits.Math.powis the way to raise a number to a power.- Compound form.
s ^= val;means the same ass = s ^ val;and is the form many Java programmers write. - Negative numbers work. Java stores
intvalues in two's complement, and XOR acts on all 32 bits.x ^ xis still 0 for negativex, so[-3, 5, -3]gives 5. - No overflow. XOR never carries between bits, so the result always fits in an
int. This is different from a sum-based approach, where the sum could in principle exceed the range ofint. - The for-each loop gives each element by value in
val. Assigning tovalwould not change the array, and the code doesn't do that.
Complexity
Time: O(n). The loop visits each of the n elements once and does one XOR per element, which takes constant time.
Space: O(1). The method uses one accumulator and the loop variable, whatever the size of the array.
Edge cases and common mistakes
- A single element. For
[1]the result is0 ^ 1 = 1. - Starting from the wrong value. Initialising
sto 1, or tonums[0]and then looping over the whole array, breaks the cancelling. The loop would XOR the first element twice. Starting at 0 and looping over every element is the simplest correct form. - Zero in the input. The lone value can be 0, as in
[0, 7, 7], and XOR gives 0 correctly. A solution that uses 0 to mean "nothing found" would be ambiguous here. - Using
+instead of^. Adding all the values doesn't cancel the pairs. They would double up instead. - The guarantee matters. This only works because every other value appears exactly twice. If one appeared three times, or two values appeared once, the XOR would no longer be the answer. For
[1, 2]it would return3, which isn't an element at all.
Testing
[2, 2, 1]gives1.[4, 1, 2, 1, 2]gives4.[1]gives1.[-3, 5, -3]gives5.[0, 7, 7]gives0.
