Task Livecoding Java Missing Number | IT Ментор

91. Поиск отсутствующего числа в массиве от 0 до n #

Условие задачи:
📌 Дан массив nums длины n, содержащий различные числа из диапазона [0, n].
Одно число из диапазона отсутствует.
Нужно вернуть это единственное отсутствующее число.

Код:

/*
        Дан массив nums, содержащий n различных чисел в диапазоне [0,n].
        Нужно вернуть единственное число в этом диапазоне, отсутствующее в массиве
        
        Пример 1:
        Ввод: nums = [3,0,1]
        Вывод: 2
        
        Пример 2:
        Ввод: nums = [0,1]
        Вывод: 2
*/

class MissingNumberSolution {
        public int findMissingNumber(int[] nums) {
        }
}

Спойлеры к решению

Подсказки

💡 Сумма чисел от 0 до n известна по формуле:
sumExpected = n * (n + 1) / 2
💡 Сравнив её с суммой массива, вы найдёте отсутствующее число.
💡 Это решение работает за O(n) времени и O(1) памяти.
💡 Альтернативный вариант — использовать XOR (тоже O(n), O(1)).

Решение

class MissingNumberSolution {

    public int findMissingNumber(int[] nums) {
        int n = nums.length;

        // сумма чисел от 0 до n
        int expected = n * (n + 1) / 2;

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

        return expected - actual;
    }
}

Альтернативное решение через XOR (быстрее на практике):

public int findMissingNumber(int[] nums) {
    int xor = nums.length; // начинаем с n

    for (int i = 0; i < nums.length; i++) {
        xor ^= i;       // XOR индексов
        xor ^= nums[i]; // XOR элементов
    }

    return xor;
}