obsidian/АиСД/Задачи/LeetCode/Missing Number.md

Leetcode #268 | #Easy | Математика

Идея

Сумма от 0 до n легко считается, вычитаем сумму данного массива и находим недостающий элемент

Big-O

• Время O(N)
• Память O(1)

Код

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int expected = n * (n + 1) / 2, actual = 0;
        for (int num : nums) actual += num;
        return expected - actual;
    }
}