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

52. Найти отсутствующее число в массиве

Условие задачи:
Дан массив 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 и вычесть сумму элементов массива.
💡 Для защиты от переполнения при вычислении суммы используй long.
💡 Альтернативное решение — применить XOR к индексам и значениям массива.
💡 XOR не требует дополнительной памяти и не подвержен переполнению.

Решение

Вариант через XOR:

class MissingNumberSolution {

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

        for (int i = 0; i < nums.length; i++) {
            result ^= i;
            result ^= nums[i];
        }

        return result;
    }
}

Одинаковые числа при применении XOR взаимно уничтожаются:

x ^ x = 0
x ^ 0 = x

В результате останется только отсутствующее число.

Альтернативный вариант через сумму:

class MissingNumberSolution {

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

        long expectedSum = (long) n * (n + 1) / 2;
        long actualSum = 0;

        for (int number : nums) {
            actualSum += number;
        }

        return (int) (expectedSum - actualSum);
    }
}

Временная сложность обоих решений — O(n), дополнительная память — O(1).