I’ve been drilling on LeetCode recently and ran into a problem which I did not know how to solve while using constant extra space:

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

  • Input: nums = [2,2,1]
  • Output: 1

Example 2:

  • Input: nums = [4,1,2,1,2]
  • Output: 4

Example 3:

  • Input: nums = [1]
  • Output: 1

The solution, it turns out, was to use the XOR bitwise operator on an int like so:

func singleNumber(nums []int) int {
    answer := 0

    for _, num := range nums {
        answer = answer ^ num
    }

    return answer
}

I didn’t initially grok how this worked until I worked through it with pen and paper. Here are some notes to Future Me™.

This relies on the fact that XORing the same number twice cancels it out.

Here is how it works with Example 2 from above: [4,1,2,1,2]

Binary | Operation
----------------

000   <-  start with 0
100   <-  xor 4

100   <-  result is 4
001   <-  xor 1

101   <-  result is 5
010   <-  xor 2

111   <-  result is 7
001   <-  xor 1 again

110   <-  result is 6
010   <-  xor 2 again

100   <-  result is 4 (the only number which appears once)

Neat!