Home/

...

/

Find the Missing Number (easy)

Find the Missing Number (easy)

Problem Statement

We are given an array containing n distinct numbers taken from the range 0 to n. Since the array has only n numbers out of the total n+1 numbers, find the missing number.

Example 1:

Input: [4, 0, 3, 1]
Output: 2

Example 2:

Input: [8, 3, 5, 2, 4, 6, 0, 1]
Output: 7

Try it yourself

Try solving this question here:

class MissingNumber {
  public static int findMissingNumber(int[] nums) {
    // TODO: Write your code here
    return -1;
  }
}

Solution

This problem follows the Cyclic Sort pattern. Since the input array contains unique numbers from the range 0 to n, we can use a similar strategy as discussed in Cyclic Sort to place the numbers on their correct index. Once we have every number in its correct place, we can iterate the array to find the index which does not have the correct number, and that index will be our missing number.

However, there are two differences with Cyclic Sort:

  1. In this problem, the numbers are ranged from 0 to n, compared to 1 to n in the
...