❔ Задача с LeetCode «Patching Array №330»

Дан отсортированный целочисленный массив nums и целое число n.

Добавьте/исправьте элементы в массиве таким образом, чтобы любое число в диапазоне [1, n] включительно могло быть образовано суммой некоторых элементов в массиве.

Верните минимальное требуемое количество исправлений.

Пример 1:
Входные данные: nums = [1,3], n = 6
Вывод: 1
Пояснение: Комбинации чисел [1], [3], [1,3] образуют возможные суммы: 1, 3, 4. Теперь, если мы добавим 2 в массив, то получим следующие комбинации: [1], [2], [3], [1,3], [2,3], [1,2,3]. Возможными суммами являются 1, 2, 3, 4, 5, 6, которые теперь охватывают диапазон [1,6]. Таким образом, нам нужно только 1 добавление.

Пример 2:
Входные данные: nums = [1,5,10], n = 20
Вывод: 2
Пояснение: Достаточно добавить 2 и 4 в массив.

Пример 3:
Входные данные: nums = [1,2,2], n = 5
Вывод: 0

📱 Java Developer | #задача #hard