Start learning free

LESSON 592 OF 673 · BIT MANIPULATION

Missing Number

Practice O(n)

You get a list nums of n different numbers. Each number is from 0 to n.

Exactly one number from 0 to n is not in nums. Return that missing number.

 

Example 1:

Input: nums = [4, 1, 0, 2]
Output: 3
Explanation: The array has 4 numbers, so n = 4.
Of the numbers 0 to 4, only 3 is missing.

Example 2:

Input: nums = [1, 3, 2]
Output: 0
Explanation: Here n = 3.
The numbers 1, 2 and 3 are all there.
The missing number is 0.

Example 3:

Input: nums = [0]
Output: 1
Explanation: Here n = 1, and 0 is in nums.
The missing number is 1, which is n itself.

 

Constraints:

  • n is the length of nums (len(nums)).
  • n is from 1 to 100,000.
  • Each value is from 0 to n.
  • No value appears twice.
Note:

Your algorithm should run in O(n) time and use O(1) extra space.



In Single Number, XOR made the pairs cancel: x XOR x = 0, x XOR 0 = x, and the order doesn't matter. Here no number repeats. Can you give every number that is in nums a partner to cancel with?

The indices of nums go from 0 to n - 1: add n and you have every number from 0 to n once. Start from n and XOR in every index and every value. Each value in nums meets its equal and cancels; the missing number has no partner among the values, so it is what is left.

We visit each index once, with two XORs per index: O(n) time.
We keep a single number, so the extra space is O(1).
STEP 1 OF 4
    Ctrl + Enter to check