Sum of Zeros and Ones

Medium

Call a positive integer *binary-looking* if its decimal form uses only the digits 0 and 1 (with no leading zeros). For instance, 1, 10 and 1101 are binary-looking, while 12 and 2001 are not. You are given a positive integer as a string number. Return the smallest count of binary-looking numbers that add up to number. The same number may be used more than once.

Example 1

number="46" → 6

46 = 11 + 11 + 11 + 11 + 1 + 1, six addends. Fewer is impossible: each addend adds at most 1 to the last digit.

Example 2

number="1010" → 1

The number itself uses only 0s and 1s, so one addend is enough.

Example 3

number="30719" → 9

Constraints

1 ≤ len(number) ≤ 10⁵
number contains digits only
number has no leading zero

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy String

Similar problems

Biggest Number From Pieces Medium Every Letter Once Medium Erase Digits for the Smallest Number Medium Smallest Up-Down Sequence Medium Ring of Flippable Words Medium

Input

number="46"

Expected

Run checks the first 3 tests in your browser. Submit checks all 75 tests on the server, hidden ones included.