Сумма чисел от 1 до 100 равна 5050. Вычтите из неё сумму элементов массива — останется отсутствующее число; нужен один проход.
Определение отсутствующего элемента в массиве
Сумма чисел от 1 до 100 равна 5050. Вычтите из неё сумму элементов массива — останется отсутствующее число; нужен один проход.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Дан массив, содержащий все числа от 1 до 100 в произвольном порядке, за исключением одного отсутствующего значения. Требуется за наименьшее возможное количество проходов по массиву определить, какое число отсутствует.
Ответ
Сумма чисел от 1 до 100 равна 5050. Вычтите из неё сумму элементов массива — останется отсутствующее число; нужен один проход.
function missingNumber(numbers) {
return 5050 - numbers.reduce((sum, value) => sum + value, 0);
}
Например, если отсутствует 100, сумма массива равна 4950. Решение опирается на гарантии: ровно 99 элементов, все из диапазона 1–100, без повторений и ровно один пропуск. Если вход этим условиям не соответствует, одна разность не позволяет отличить отсутствие от дубликатов. Время O(n), дополнительная память O(1).