easy

Missing Number

Find the one number missing from a list containing n distinct numbers from 0 to n.

1. Define the problem

Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the one number in that range that is missing from nums. XOR every index together with every value , plus n itself. Every number that is actually present cancels its own index, leaving only the missing number.

Constraints

  • n == nums.length
  • 1 ≤ n ≤ 104
  • 0 ≤ numsi ≤ n
  • All values are distinct

Example

Inputnums = [3, 0, 1]
Output2

Explanation n = 3, and the range [0, 3] is missing the number 2.

2. Know the words first

In plain terms

XOR
XOR-ing a value with itself gives 0. If every index from 0 to n and every value in nums is XORed together, every present number cancels against its own index — only the missing one has nothing to cancel it.
3. Visualize the solution

XOR every index and value into one running result

XOR every index and value into one running result
Statusinit

result = n = 3. XOR with index 0 and nums[0]=3: 3 ^ 0 ^ 3 = 0.

What happens in this step

result = n = 3

i ^ nums[i] = 0 ^ 3
  0 = 00000000
  3 = 00000011
      --------
      00000011  =  3

result ^= 3
  3 = 00000011
  3 = 00000011
      --------
      00000000  =  0

Index 0 and its value 3 combine to 3, then merge into result. Result also started at 3, so the two 3s cancel — result becomes 0.
Step 1 of 4

Steps to visualize

  1. Start a running result at n (the length of nums).
  2. For each index i, XOR the result with i and with numsi.
  3. Every number that appears in nums cancels out against its matching index.
  4. What remains after the last index is the missing number.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

XOR every index and value into one running result
Statusinit

result = n = 3. XOR with index 0 and nums[0]=3: 3 ^ 0 ^ 3 = 0.

What happens in this step

result = n = 3

i ^ nums[i] = 0 ^ 3
  0 = 00000000
  3 = 00000011
      --------
      00000011  =  3

result ^= 3
  3 = 00000011
  3 = 00000011
      --------
      00000000  =  0

Index 0 and its value 3 combine to 3, then merge into result. Result also started at 3, so the two 3s cancel — result becomes 0.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function missingNumber(nums) {
  let result = nums.length;

  for (let i = 0; i < nums.length; i++) {
    result ^= i ^ nums[i];
  }

  return result;
}
Time
O(n)
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
nums = [3, 0, 1]2example from the docstring
nums = [0, 1]2the missing number is the largest value in the range
nums = [1, 2, 3]0the missing number is 0
nums = [1]0smallest valid input, single element
nums = [0]1smallest valid input, missing the only other value
nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]8the missing number sits in the middle of the range

Keep reading