Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Find the Missing Number

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

Constraints:

  • n == nums.length
  • 1 <= n <= 10^4
  • 0 <= nums[i] <= n
  • All the numbers of nums are unique.

Solution

This problem follows the Cyclic Sort pattern

.....

.....

.....

Like the course? Get enrolled and start learning!
G

Gideon

· 4 years ago

One way to look at this is:

Place all numbers in their correct position except n.

At the end, n will be at the missing index.

if n is the missing number, all other numbers will be in the correct position, hence return n at the end.

Show 1 reply
K

Kyle McKee

· 4 years ago

Why not compare i and j directly instead of doing nums[i] and nums[j]? Since the array contains distinct numbers nums[i] would never equal nums[j] unless i and j are equal, correct?

Show 1 reply
A

Athanasios Petsas

· 4 years ago

An alternative solution if we consider that the sum of numbers: 1, 2, 3, ..., n is 1 + 2 + 3 + ... + n = n * (n+1) / 2, would be to sum all numbers in the loop and return n*(n+1)/2 - sum. Of course it has the same time complexity O(N) and and space complexity O(1) but it's only one pass. I know that the specific lesson follows this approach to demonstrate the pattern and to group similar problems under the same umbrella. I just thought of that solution when saw the problem, that's why I'm posting it here. Quick python code: {code} def find_missing_number(nums): n = len(nums) s = 0 for num in nums: s += num return (n * (n+1) // 2) - s {code}

Show 2 replies
Fei Shan

Fei Shan

· 2 years ago

int findMissingNumber2(int[] nums) {

    int total = ( 0 + nums.length ) * (nums.length + 1) / 2;
    int sum = Arrays.stream(nums).sum();

    return total - sum;

}
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def findMissingNumber(self, nums):
    
    def swap(i, j):
       nums[i], nums[j] = nums[j], nums[i]
    
    # try to position each element such as nums[i] == i. 
    # the max element can not placed as nums[i] == i.
    # e.g. [4, 0, 3, 1] max = 4 
    # as result of placing all the elements you will have the max in the missing index i. 
    for i in range(len(nums)):
      while nums[i] != i and nums[i] != len(nums):
        swap(i, nums[i])

    for i in range(len(nums)):
      if nums[i] == len(nums):
        return i

    return len(nums)
N

nrstnbr

· 4 years ago

I feel like the examples are a bit misleading here. Would be useful to have another example to indicate that cyclic sort is useful

Daehan Choi

Daehan Choi

· 2 years ago

public static int findMissingNumber(int[] nums) {
    boolean[] checks = new boolean[nums.length + 1];
    for (int num: nums) {
        checks[num] = true;
    }
    for (int i = 0; i < checks.length; i++) {
        if (!checks[i]) return i;
    }
    return -1;
}
Faraz Ahmed

Faraz Ahmed

· a day ago

does nums[i] < n matter? when we are already checking the permissable range in while loop condition i<n