< Back




136. Single Number

We're given an array of integers where every single integer appears twice except for one. We're
asked to find it. This is an array question, but it's also a bit manipulation question. We'll
maintain a running scalar variable that keep the result of an XOR operation between the scalar
variable and the current number in the array. Because of the nature of XOR, duplicate numbers in the
input will cancel each other out. Eventually, the integer with no duplicate will remain in the
scalar variable.

The solution is as follows:


  class Solution:
      def singleNumber(self, nums: List[int]) -> int:
          ans = 0

          for num in nums:
              ans ^= num

          return ans


_ Time Complexity:

  O(n) - We process all integers in the input.

_ Space Complexity:

  O(1) - We maintain a single scalar variable.