[Leetcode problems]136. Single Number

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.

XOR

  1. Commutative: A ⊕ B = B ⊕ A
  2. Associative: A ⊕ ( B ⊕ C ) = ( A ⊕ B ) ⊕ C
  3. Identity element: A ⊕ 0 = A
  4. Self-inverse: A ⊕ A = 0

Therefore, given different numbers as [a,b,c,a,b], we have

a \oplus b \oplus c \oplus a \oplus b =a \oplus a \oplus b \oplus b \oplus c =c

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)

Reference

https://accu.org/index.php/journals/1915

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments