Ctrl K

Прибавить или удвоить всё

Средняя
На табло горят счётчики, сначала все равны нулю. Пульт умеет две вещи: - **прибавить** — увеличить на 1 один выбранный счётчик; - **удвоить** — умножить на 2 сразу все счётчики. Каждое действие — одно нажатие. Дан массив target: сколько должно оказаться на каждом счётчике в конце. Верните наименьшее число нажатий, за которое табло можно привести к target.
Пример 1
target=[3, 4] → 5

[0, 0] → +1 второму: [0, 1] → удвоение: [0, 2] → +1 первому: [1, 2] → удвоение: [2, 4] → +1 первому: [3, 4]. Всего 5 нажатий.

Пример 2
target=[0, 0, 7] → 5

[0, 0, 1] → удвоение → [0, 0, 2] → [0, 0, 3] → удвоение → [0, 0, 6] → [0, 0, 7]: три прибавления и два удвоения.

Пример 3
target=[8] → 4

Одно прибавление и три удвоения: 1 → 2 → 4 → 8.

Ограничения
  • 1 ≤ len(target) ≤ 10⁵
  • 0 ≤ target[i] ≤ 10⁹
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиМаксимум двоичных строк после переворотов СредняяКомпании по четыре в кинозале СредняяУдвоения ради наибольшего OR СредняяСамая сильная команда СредняяБольше кусков с нулевым AND Средняя
загружаем Python…
Вход
target=[3, 4]
Ожидается
5

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