Missing Number

https://leetcode.com/problems/missing-numberEasy

Условие

Дан массив nums, содержащий n уникальных чисел, находящихся в диапазоне от 0 до n. Найдите недостающее число.

Примеры

Input: nums = [3, 0, 1]

Output: 2

Explanation: n = 3, и у нас есть числа 0, 1, 3. Таким образом, недостающее число = 2.
Input: nums = [0, 1]

Output: 2

Explanation: n = 2, и у нас есть числа 0, 1. Таким образом, недостающее число = 2.
Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]

Output: 8

Explanation: n = 9, и у нас есть числа от 0 до 9. Таким образом, недостающее число = 8.

Решение

fun missingNumber(nums: IntArray): Int {
    val n = nums.size // Длина массива равна n
    val expectedSum = n * (n + 1) / 2 // Ожидаемая сумма от 0 до n
    val actualSum = nums.sum() // Сумма элементов в массиве
    return expectedSum - actualSum // Недостающее число
}

Временная сложность

O(n), где n — количество элементов в массиве, так как мы проходим по всем элементам для вычисления суммы.

Пространственная сложность

O(1), так как мы используем фиксированное количество дополнительных переменных.