Определение отсутствующего элемента в перемешанном массиве

Условие

Имеется упорядоченный набор целых чисел от 1 до N. Один из элементов был удалён, а оставшиеся числа перемешаны в произвольном порядке. Необходимо найти удалённое число.

Ответ

Вычислите XOR всех чисел 1…N и всех элементов массива: одинаковые значения взаимно уничтожатся, останется пропущенное. При корректном условии N равно длине массива плюс один.

static int missing(int[] nums) {
    int n = Math.addExact(nums.length, 1);
    int result = n;
    for (int i = 0; i < nums.length; i++)
        result ^= (i + 1) ^ nums[i];
    return result;
}

Время O(n), дополнительная память O(1), арифметическая сумма не переполняется, поскольку не вычисляется. Для пустого массива ответ 1. Алгоритм опирается на отсутствие дубликатов и ровно один пропуск в диапазоне; сам он не валидирует эти предусловия.