Ctrl K

Добрать до нужной суммы

Средняя
Дан массив целых чисел values и два числа cap и target. В массив можно дописывать новые целые числа, но каждое из них должно быть по модулю не больше cap. Верните наименьшее количество чисел, которое нужно дописать, чтобы сумма массива стала равна target.
Пример 1
values=[3, -2, 4], cap=4, target=15 → 3

Сумма сейчас 5, не хватает 10. Например, добавим 4, 4 и 2 — трёх чисел достаточно, двух мало: 4 + 4 = 8 < 10.

Пример 2
values=[1, 1], cap=10, target=-3 → 1

Сумма 2, нужно уменьшить её на 5 — достаточно добавить -5.

Пример 3
values=[2, -2], cap=3, target=0 → 0

Сумма уже равна target, добавлять ничего не нужно.

Ограничения
  • 1 ≤ len(values) ≤ 10⁵
  • 1 ≤ cap ≤ 10⁶
  • -10⁶ ≤ values[i] ≤ 10⁶
  • -10⁹ ≤ target ≤ 10⁹
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиДве доски и вода СредняяМеньше всего прыжков до конца СредняяДобраться до последней клетки СредняяСколько угодно сделок СредняяОткуда начать круг Средняя
загружаем Python…
Вход
values=[3, -2, 4], cap=4, target=15
Ожидается
3

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 107 тестов на сервере, включая скрытые.