Single Number

The problem

nums is a list of whole numbers. One number appears exactly once. Every other number appears exactly twice, and its two copies can be anywhere in the list. Return the number that appears once. The numbers can be negative or 0, and the list may hold only that one number. Apart from nums, use only a constant amount of memory, however long the list is.

What to write

function solve(nums: number[]): number

Input
nums = [2,2,1]

Output
1

Input
nums = [4,1,2,1,2]

Output
4

Constraints

1–10,001 signed 32-bit integers; all but one appear exactly twice.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   There can be 10,001 numbers, and apart from the list you may keep only a constant amount of memory. A record of the numbers you have seen grows with the list, so it is ruled out. Whatever you carry from one number to the next has to stay the same small size.

2. Hint 2: Ask a smaller question

   Think of a light switch: press it twice and it is back where it started. Give each value in 4, 1, 2, 1, 2 its own switch, all off, and press a value's switch each time you meet that value. Which switch is on at the end? How could you get that effect without one switch per value?

3. Hint 3: Name the pattern

   A number is stored as bits: a row of switches, each 0 or 1. From the left, three bits are worth 4, 2 and 1, so 101 is 5. Exclusive or (XOR, written ^) flips one number's bits wherever the other has a 1: 100 ^ 001 = 101. Pairs that undo each other with nothing remembered signal bit manipulation. Read the lesson on bit manipulation.

4. Hint 4: State the invariant

   After each number, the running result is the XOR of everything read so far. Flips can be made in any order, so a number read twice has flipped its bits and flipped them back. What remains is the XOR of the numbers read only once so far. At the end that is a single number.

5. Hint 5: Sketch the pseudocode

   Set result to 0. For each number in nums, replace result with result XOR that number. After the last number, return result. Starting at 0 is safe: every bit of 0 is off, so the first XOR turns on exactly the bits of the first number.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

XOR all the numbers together, where XOR (exclusive or, written ^) flips one number's bits wherever the other has a 1. The two copies of a number cancel, so what is left is the number that appears once.

The slow way

For each number, walk the whole list and count how often that number appears. Return the one counted once. It is correct and needs almost no memory, but 10,001 numbers can cost about 100 million comparisons. A set of the numbers seen so far is fast, but it grows with the list, which the statement rules out. The tests here cannot check memory, so a set still passes them.

The insight

A number is stored as a row of bits, each 0 or 1. From the left, three bits are worth 4, 2 and 1, so 5 is 101 and 3 is 011. Exclusive or, called XOR and written ^, flips one number's bits wherever the other has a 1: 101 ^ 011 = 110. XOR with 011 again flips them back: 101. So a pair undoes itself.

Step by step

1. Start the running result at 0. Every bit of 0 is off, so the first XOR turns on exactly the bits of the first number. Any other start would leave its own bits mixed into the answer.
2. XOR each number into the running result. A number flips the result's bits wherever that number has a 1. Its second copy flips the same bits back, however many other numbers come between the two copies.
3. Return the running result, the number without a pair. Every paired number has flipped its bits twice and left no mark. The only flips never undone belong to the number that appears once, so the result is that number.

The same numbered steps are the comments in each solution.

function solve(nums) {
  // 1. Start the running result at 0
  let result = 0;
  // 2. XOR each number into the running result
  for (const num of nums) {
    result ^= num;
  }
  // 3. Return the running result, the number without a pair
  return result;
}

function solve(nums: number[]): number {
  // 1. Start the running result at 0
  let result = 0;
  // 2. XOR each number into the running result
  for (const num of nums) {
    result ^= num;
  }
  // 3. Return the running result, the number without a pair
  return result;
}

def solve(nums):
    # 1. Start the running result at 0
    result = 0
    # 2. XOR each number into the running result
    for num in nums:
        result ^= num
    # 3. Return the running result, the number without a pair
    return result

Example 2, traced

Input
nums = [4,1,2,1,2]

Output
4

Why it works

A bit that is flipped twice ends where it began, and flips can be made in any order. Every paired number flips its bits twice, so the pairs cancel, wherever their copies sit in the list. What is left is 0 with the bits of the single number turned on, which is that number. Negative numbers are rows of bits too, so nothing changes for them.

Time and space

Time O(n), extra space O(1). The loop makes one pass: it reads each of the n numbers once and does one XOR for it, so the time is O(n). Only the running result is kept, one number however long the list is, so the extra space is O(1).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Start the result at 0. If it starts as the first number and the loop still reads the whole list, that number goes in once too often: 2, 2, 1 XORs 2 three times and returns 3 instead of 1.
• The operator is ^, not |. The | operator is called or: it can turn bits on but never off, so nothing ever cancels. With it, 4, 1, 2, 1, 2 returns 7 instead of 4.

Pattern

Bit manipulation.

Keep going