Leetcode # 136. Single Number

https://leetcode.com/problems/single-number/

XOR

\begin{align}
1. \, & p \oplus 0 = p \\
2. \, & p \oplus p = 0 \\
3. \, & 有交換律： p \oplus q = q \oplus p \\
& \Rightarrow  p \oplus q \oplus p = p \oplus p \oplus q = 0 \oplus q = q \\
\end{align}

Solution

Time Complexity: O(n)
Space Complexity: O(1)

class Solution:
  def singleNumber(self, nums: List[int]) -> int:
    a = 0
    for num in nums:
      a ^= num
    return a

Last Updated on 2023/08/16 by A1go