Я вернулся с руководством по еще одному распространенному техническому вопросу на собеседовании. На этот раз мы будем решать проблему отсутствующего числа, которая ставит перед вами задачу найти недостающее число в несортированном массиве.

-— Directions
You're given an unsorted array of numbers in a sequence from 1 to n with one of the numbers missing. Create a function that takes the unsorted array as an argument and returns the number that is missing from the array.
-- Example
const a = [2, 1, 5, 4]
missingNum(a) // 3;

Эта проблема немного сложнее, чем некоторые из тех, которые мы рассматривали ранее, но, как и в случае с большинством других проблем, как только вы обнаружите уловку для ее решения, это станет намного проще.

Итак, давайте, как всегда, начнем с определения нашей функции.

Мы знаем, что array - это несортированный список последовательных номеров от 1 до n, в котором отсутствует один номер. В настоящее время значение n нам неизвестно, но его можно легко вывести, используя информацию в описании проблемы.

Поскольку массив состоит из чисел от 1 до n и в нем отсутствует только одно число, то мы можем объявить n равным array.length + 1.

На этом этапе вы все еще можете не знать, как мы будем искать недостающее число в нашем массиве от 1 до n; но что, если бы мы знали значение n?

Например, вместо того, чтобы состоять из элементов от 1 до n, давайте представим, что array состоит из чисел от 1 до 4. Найти недостающее число в этом массиве будет просто, потому что все, что нам нужно сделать, это вычислить сумму чисел от 1 до 4 и вычесть сумму всех элементов в array. Оставшееся значение будет числом, отсутствующим в массиве.

Эта же идея работает для массивов в диапазоне от 1 до n, но нам понадобится способ вычислить сумму от 1 до n. Введите: математик Карл Фридрих Гаусс.

Гауссу приписывают создание формулы для нахождения суммы последовательности чисел или ряда. Формула записывается как (n*(n + 1)) / 2.

Объявив переменную для total от 1 до n, мы можем начать решение проблемы с вычисления суммы элементов в array. Как мы это делаем? Конечно, перебирая каждый элемент!

Сначала мы объявим переменную sum, равную 0. Затем мы создадим for loop для перебора каждого элемента в array. На каждой итерации мы будем добавлять значение текущего элемента к sum.

После того, как итерация выполняется для всей длины array, переменная sum будет представлять сумму всех элементов вместе. Когда объявлены и вычислены переменные total и sum, последний шаг - выйти из for loop и вернуть разницу между двумя переменными.

Определив missingNum, пора проверить, работает ли функция должным образом. Я создал три массива разной длины, каждый из которых состоит из последовательности чисел, в которой отсутствует одно число. Запуск missingNum с каждым из этих массивов правильно возвращает отсутствующее целое число.

Вывод

Решение технического вопроса собеседования на отсутствующее число может оказаться невозможным без знания формулы Гаусса. Если вы не смогли решить эту проблему самостоятельно до прочтения этого руководства, ничего страшного! Теперь у вас есть знания, которые помогут вам справиться с подобными вопросами на собеседовании.

И если вы смогли вывести часть этого ответа, например, зная, что вам нужно вычесть сумму элементов массива из общей суммы от 1 до n, это отличное начало! Знание того, как решить проблему, даже если вы на самом деле не даете правильный ответ, - отличный способ продемонстрировать свое логическое мышление и навыки решения проблем. интервьюер.