Problem overview
singleNumber(nums []int) receives a non-empty slice in which every number appears exactly twice, except for one number that appears once. It returns that single number. The lesson asks for O(n) time and O(1) extra space.
For nums = [2, 2, 1] the answer is 1. For [4, 1, 2, 1, 2] it is 4, and for [1] it is 1. Values can be negative.
Approach: XOR cancels the pairs
The obvious solutions each give something up. Sorting costs O(n log n) time. A map of counts is O(n) time but needs O(n) space. The bound of O(n) time with O(1) space points to a trick on the numbers themselves.
The trick is the bitwise XOR operator, written ^ in Go. It compares two numbers bit by bit and produces a 1 wherever the bits differ. Two of its properties do the work:
x ^ x == 0: a number XORed with itself disappears.x ^ 0 == x: XOR with zero changes nothing.
XOR is also commutative and associative, so the order of the operands doesn't matter and the two copies of a number don't have to be next to each other. XOR all the numbers together, and every pair cancels to 0. The single number is left.
For [4, 1, 2, 1, 2] the running value goes 0, 4, 5, 7, 6, 4. In other words, 4 ^ 1 ^ 2 ^ 1 ^ 2 regroups as 4 ^ (1 ^ 1) ^ (2 ^ 2), which is 4 ^ 0 ^ 0, and that is 4.
Step by step
- Declare the accumulator with
s := 0. Zero is the starting value because XOR with 0 leaves any number unchanged. It becomes anint, the same type as the elements ofnums. - Loop over the slice with
for _, val := range nums.rangegives an index and a value for each element, and the_discards the index. - Fold each number in with
s = s ^ val. - Return
s. After the loop, it holds the number that had no partner.
The solution in Go
func singleNumber(nums []int) int {
s := 0
for _, val := range nums {
s = s ^ val
}
return s
}
The Go details worth a closer look:
^as XOR. Between two operands,^is XOR. Go also has^xwith one operand, which flips every bit, so the meaning depends on whether there is a left operand. The compound forms ^= valis the same ass = s ^ val.- Negative numbers work. Go stores
intvalues in two's complement, and XOR works on all the bits, sign included.singleNumber([]int{-3, 5, 5})returns -3. :=infers the type. The literal0givessthe typeint. No cast is needed against the slice's elements.- The loop variable is a copy.
valholds a copy of the current element, which is fine here, because the slice is only read. - Unused names don't compile. If the index were declared as
iand never used, the build would fail withdeclared and not used. That is why the code writes_.
Complexity
Time: O(n). The loop makes a single pass, with one XOR per element.
Space: O(1). The only extra storage is the integer s and the loop's own variables. Nothing grows with the input.
Edge cases and common mistakes
- A single element.
[1]gives0 ^ 1, which is 1. - The single number comes first, last or in the middle. Position makes no difference, because XOR ignores order.
- Negative values. They cancel in pairs the same way as positive ones.
- Starting from a nonzero value. The starting value would stay in the result. Start at 0.
- Relying on it elsewhere. The method needs every other number to appear an even number of times. If the others appeared three times, XOR would not cancel them, and that variant needs a different idea.
- Empty input. The problem guarantees at least one number. An empty slice would return 0, which is not a valid answer.
Testing
nums = [2, 2, 1]gives1.nums = [4, 1, 2, 1, 2]gives4.nums = [1]gives1.nums = [-3, 5, 5]gives-3.
