Сумма из нулей и единиц

Средняя

Назовём положительное число *двоичноподобным*, если в его десятичной записи встречаются только цифры 0 и 1 (и нет ведущих нулей). Например, 1, 10 и 1101 двоичноподобны, а 12 и 2001 — нет. Дано положительное целое число в виде строки number. Верните наименьшее количество двоичноподобных чисел, сумма которых равна number. Одно и то же число можно использовать несколько раз.

Пример 1

number="46" → 6

46 = 11 + 11 + 11 + 11 + 1 + 1: шесть слагаемых. Меньше нельзя — каждое слагаемое добавляет к младшему разряду не больше единицы.

Пример 2

number="1010" → 1

Число само состоит из нулей и единиц, так что хватит одного слагаемого.

Пример 3

number="30719" → 9

Ограничения

1 ≤ len(number) ≤ 10⁵
number состоит только из цифр
number не начинается с нуля

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Greedy String

Вход

number="46"

Ожидается

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