How to find the missing number in a given integer array of 1 to 100? -

Premise

This is a somewhat common interview question that asks the following. Consider there is an array holding sorted numbers in an established range. For our example, we’ll propose numbers ranging from 1 to 100. No duplicate elements are allowed. Also, there is only one element missing. What is that element? Or to rephase it – how to find the missing number in a given integer array?

Solution

First of all, let us think about the premise of the question. We are validating we only have one element missing, that the data structure holding the numbers is sorted, and that no duplicate elements are allowed.

One possible solution to the problem could be using the sum of natural numbers. Below we have a formula for the sum of n natural numbers. We will use this formula to leverage the sum of the n natural numbers, and it can be applied to arrays of varying lengths.

{\frac{n * (n + 1)}{2}}

Why this formula though? Well, if we sum the first number and the n-th number, we would get (n + 1). If we sum the second number and the n - 1 number, we would get (n + 1). If we keep this, adding numbers from start to end, we’ll keep getting (n + 1). In total, we would have n amount of pairs! When we multiply the n amount of pairs with (n + 1) (continuous sum of first and last elements) we’ll count each pair twice. Diving by two corrects this.

So, for the input number of 5, we expect the sum of numbers to be 15. IF all the numbers were present. If not, we just subtract the existing sum from the expected sum and that is our missing number!

Below is a solution to this problem written in JS and Python. We reduced the input size to 10 elements for brevity’s sake. Both snippets follow the same methodology. We create the sum of integers for the provided size. Afterwards, we subtract the current sum from the expected and we return this number. We also handle the edge case in which we have the full range provided!

function findMissingNumber(arr, arrSize) {
    const n = arrSize;
    const expectedSum = (n * (n + 1)) / 2;
    const actualSum = arr.reduce((sum, num) => sum + num, 0);
    const missingNumber = expectedSum - actualSum;
    return missingNumber;
}

findMissingNumber([1, 2, 3, 4, 6, 7, 8, 9, 10], 10);
findMissingNumber([1, 2, 3, 4, 5, 6, 7, 8, 9], 10);
findMissingNumber([1, 2, 4, 5, 6, 7, 8, 9, 10], 10);
findMissingNumber([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 10);

def find_missing_number(arr, arr_len):
    n = arr_len
    expected_sum = (n * (n + 1)) // 2 
    actual_sum = sum(arr)
    missing_number = expected_sum - actual_sum
    return missing_number


find_missing_number([1, 2, 3, 4, 6, 7, 8, 9, 10], 10);
find_missing_number([1, 2, 3, 4, 5, 6, 7, 8, 9], 10);
find_missing_number([1, 2, 4, 5, 6, 7, 8, 9, 10], 10);
find_missing_number([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 10);

Facebook Tweet Pin LinkedIn