268. Missing Number

Задача

Дан массив nums, содержащий n уникальных чисел в диапазоне [0, n]. Верните единственное число из этого диапазона, которое отсутствует в массиве.

Примеры

Пример 1

Input: nums = [3,0,1]
Output: 2

Пояснение

n = 3, все числа в диапазоне [0,3]. 2 — отсутствующее число, так как оно не встречается в nums.

Пример 2

Input: nums = [0,1]
Output: 2

Пояснение

n = 2, все числа в диапазоне [0,2]. 2 — отсутствующее число.

Пример 3

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8

Пояснение

n = 9, все числа в диапазоне [0,9]. 8 — отсутствующее число.

Решение

Решение

/**
 * Временная сложность: O(n)
 * Пространственная сложность: O(1)
 */
var missingNumber = function(nums) {
    let xor = 0;
 
    // XOR всех индексов (от 0 до n) и всех значений
    // i идет до n (включительно для индекса как числа диапазона)
    for (let i = 0; i <= nums.length; i++) {
        xor = xor ^ i; // XOR с числом из полного диапазона
 
        if (i < nums.length) {
            xor = xor ^ nums[i]; // XOR с числом из массива
        }
    }
 
    return xor;
};

Решение 2 (Прогрессия)

/**
 * Мы знаем, что сумма чисел от 0 до n вычисляется по формуле арифметической прогрессии: S = n * (n + 1) / 2.
 * Если вычесть из этой ожидаемой суммы реальную сумму элементов массива, остаток и будет искомым числом.
 
 * Временная сложность: O(n) - один проход для суммы
 * Пространственная сложность: O(1) - только переменные
 */
var missingNumber = function(nums) {
    const n = nums.length;
    const expectedSum = (n * (n + 1)) / 2;
    let actualSum = 0;
 
    for (const num of nums) {
        actualSum += num;
    }
 
    return expectedSum - actualSum;
};

Решение 3 (Set)

/**
 * Временная сложность: O(n) - создание Set требует прохода по массиву, и второй цикл тоже O(n).
 * Пространственная сложность: O(n) - мы храним все n элементов в памяти (в структуре Set).
 */
var missingNumber = function(nums) {
    const numSet = new Set(nums);
    const n = nums.length;
 
    // Проверяем каждое число из полного диапазона [0, n]
    // Тот элемент, которого нет в Set, и есть пропущенный.
    for (let i = 0; i <= n; i++) {
        if (!numSet.has(i)) {
            return i;
        }
    }
 
    return -1; // Теоретически недостижимый код при корректных входных данных
};