#Q41: Smallest missing number in array

Write a function that outputs the smallest missing number in a sorted array of n unique integers. The integers in the array range from 0 to m-1, where m > n.

The function should be called 0SmallestMissingNumber

and the 3 inputs are:

1. the array
2. the “start value” of the array
3. the length of the array — 1

For example:

#Input: [0, 1, 3, 4, 8, 9], n = 0, m = 10
#Output: 2

-Credit to: team@interviewqs.com

TRY IT YOURSELF

ANSWER

This is a standard question that tests your ability to code a function in Python to properly complete a task. Since there are many ways to complete the requested task, we will settle on an easy to implement solution involving sets. Usually, when asked to solve these it is best to talk with the interviewer through the problem and mention potential edge cases you can think up.

First we will define our function as the question specifies with three arguments: array, start_value, array_length. Next, we will create a variable inside the function space to hold the set of the array input, using the set() function. Similarly, we will create another variable to hold the set of the range of values between the start_value and the array_length. This can be done using the range() function. Finally, we will take the difference between the sets using a simple subtraction call and then convert the set back into a list by calling the list() function, followed by sorting the list using .sort() and taking the first index for the solution.

def SmallestMissingNumber(array, start_value, array_length):
   arr_set = set(array)
   range_set = set(range(start_value, array_length + 1))
   s = list(range_set-arr_set)
   s.sort()
   return s[0]