Given a non-empty array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? Example 1: Input: [2,2,1] Output: 1
We could sort it first and find the answer in one pass (time complexity O(nlogn); space complexity O(1)). Or, we can use a hashmap to record the number of appearances to find the number with 1 appearance (time complexity O(n); space complexity O(n)).
Noticing the follow-up requires O(n) time complexity and O(1) space complexity, we would need to use bitwise operators: XOR.
- Commutative: A ⊕ B = B ⊕ A
- Associative: A ⊕ ( B ⊕ C ) = ( A ⊕ B ) ⊕ C
- Identity element: A ⊕ 0 = A
- Self-inverse: A ⊕ A = 0
Therefore, given different numbers as
[a,b,c,a,b], we have
With this being said, all we need to do is to apply XOR to input one by one. Python code is as follows:
def singleNumber(self, nums: List[int]) -> int: return reduce(lambda x,y:x^y,nums)