Задача: найти недостающий элемент массива

Решаем задачи, которые дают программистам на собеседованиях в IT‑компаниях. Сегодня ищем, какого элемента не хватает в массиве.

Иллюстрация: Polina Vari для Skillbox Media

Дмитрий Зверев

Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.

Сергей Голицын

Senior Java Developer в Covalent Inc. и преподаватель. Больше семи лет в Java-разработке. В свободное время судит хакатоны и делится опытом с начинающими программистами. Пишет статьи для «Хабра» и Medium. Ведёт телеграм-каналы «Полезные ссылки около Java» и Cracking code interview.

Условие. Дан массив целых чисел nums, в котором должны содержаться все числа из диапазона [0, n]. При этом n равно числу элементов в массиве, а значит, одного элемента всегда будет не хватать. Необходимо написать функцию, которая возвращает недостающее число из этого диапазона.

Ввод и вывод. Пример 1

Ввод: nums = [3,0,1]
Вывод: 2
Пояснение: n = 3, так как всего элементов в массиве три, поэтому все элементы 
находятся в диапазоне [0,3]. 2 — недостающий элемент.

Пример 2

Ввод: nums = [0,1]
Вывод: 2
Пояснение: n = 2, так как всего элементов в массиве два, поэтому все элементы 
находятся в диапазоне [0,2]. 2 — недостающий элемент.

Пример 3

Ввод: nums = [9,6,4,2,3,5,7,0,1]
Вывод: 8
Пояснение: n = 9, так как всего элементов в массиве девять, поэтому все элементы 
находятся в диапазоне [0,9]. 8 — недостающий элемент.

Решить эту задачу самостоятельно и на разных языках программирования можно на LeetCode. Наше решение взято из телеграм-канала Сергея Cracking code interview.

Решение

Нам нужно найти недостающее число. Из условия задачи мы знаем, что все элементы уникальные, то есть не повторяются. Поэтому если у нас есть, например, массив с размером в три элемента, то его элементы должны быть такими: [0, 1, 2, 3]. Однако размер у него 3, а значит, один из элементов всегда будет пропущен и массив будет выглядеть примерно так: [1, 0, 3].

Все элементы нашего массива всегда статичны, а значит, мы можем посчитать «идеальную» сумму всех элементов (в нашем случае от 1 до 3) и вычесть из неё сумму имеющихся в массиве чисел. Так мы найдём недостающее число:

public int missingNumber(int[] nums) {
    int realSum = 0;
    int sum = 0;

    for (int num : nums) {
        sum += num;
    }

    for (int i = 0; i <= nums.length; i++) {
        realSum += i;
    }
    return realSum - sum;
}

Это решение можно немного оптимизировать и задействовать всего один цикл for:

public int missingNumber(int[] nums) {
    int rez = 0;
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += (i + 1);
        rez += nums[i];
    }
    return sum - rez;
}