Problem overview
The method singleNumber receives a non-empty array of integers in which every value appears exactly twice, except for one value that appears once. It returns that single value.
For [2, 2, 1] the answer is 1. For [4, 1, 2, 1, 2] it is 4, and for [1] it is 1.
The lesson asks for O(n) time and O(1) extra space. That rules out sorting, which takes O(n log n), and a dictionary or set of the values seen, which needs extra memory that grows with the input.
Approach: XOR cancels duplicates
XOR, written ^ in Swift, compares two integers bit by bit and produces a 1 where exactly one of the bits is 1. Three properties are enough to solve this problem:
x ^ x = 0: a value cancels itself.x ^ 0 = x: XOR with zero leaves a value unchanged.- XOR is commutative and associative, so the order of the values doesn't matter.
Combine all the numbers with XOR, starting from 0. Because the order doesn't matter, the two copies of each repeated value can be thought of as meeting each other, wherever they sit in the array, and cancelling to 0. Everything cancels except the single value, and x ^ 0 = x leaves it untouched.
For [4, 1, 2, 1, 2], the running value after each element is:
4
5
7
6
4
The final value is 4. The last two steps undo the earlier 1 and 2: 7 ^ 1 is 6, and 6 ^ 2 is 4. The intermediate values mean nothing on their own. Only the final result matters.
Step by step
- Declare an accumulator.
var s = 0holds the running XOR. It starts at 0 because0 ^ x = x, so the first element goes in unchanged. It is avarbecause it changes in the loop. - Loop over the array with
for val in nums. Each pass gives one integer. - Fold each value in:
s = s ^ val. A value met for the second time cancels the first copy. - Return
safter the loop. Only the unpaired value is left in it.
The solution in Swift
class Solution {
func singleNumber(_ nums: [Int]) -> Int {
var s = 0
for val in nums {
s = s ^ val
}
return s
}
}
The Swift details worth a closer look:
^is XOR on integers. In Swift it is the bitwise XOR operator for every integer type. It is not exponentiation, which Swift doesn't have as an operator.5 ^ 5is 0 and5 ^ 0is 5.- The compound form
s ^= valdoes the same ass = s ^ val. The lesson writes the longer form to make the idea visible. - Negative numbers work. XOR operates on the bits of the two's complement representation, and equal values still cancel:
-3 ^ -3is 0. For[-7, 4, 4, 9, 9]the method returns -7. - No overflow trap. Swift's
+stops the program on overflow, but XOR can't overflow. Its result always fits the type of its operands. valis a constant per pass. The loop variable of afor-inloop can't be reassigned inside the loop, and the code doesn't need to.- The array is not modified. The parameter is a read-only array, and the loop only reads from it.
Complexity
Time: O(n). The loop makes one pass over the n elements, with one XOR per element.
Space: O(1). The only extra storage is the integer s and the loop variable.
Edge cases and common mistakes
- One element.
[1]gives0 ^ 1, which is 1. - The single value comes first, last or in the middle. The position is irrelevant, because XOR doesn't depend on order.
- Negative values. They cancel just like positive ones.
[-3, 5, -3]gives 5. - Starting from a value other than 0. The accumulator must start at 0. Any other start leaves that start value mixed into the answer.
- Using
+or-to combine. Sums don't cancel pairs. The sum of a pair is not zero, and it can overflow for large inputs. - Expecting this to work for three copies. The cancelling relies on every other value appearing an even number of times. If a value could appear three times, one copy would survive, and the method would return a wrong value. The lesson's input rules out that case.
Testing
nums = [2, 2, 1]returns1.nums = [4, 1, 2, 1, 2]returns4.nums = [1]returns1.nums = [-3, 5, -3]returns5.nums = [-7, 4, 4, 9, 9]returns-7.
