Binary String Made of Powers of Five

Medium

You are given a string bits made of the characters 0 and 1. Cut it into consecutive pieces so that each piece is the binary form of some power of five (1, 5, 25, 125, …) and does not start with a zero. Return the smallest possible number of pieces. If the string cannot be cut this way, return -1.

Example 1

bits="1100101" → -1

The zeros at positions 2 and 3 must belong to a piece that starts earlier. The only such piece that is a power of five is "11001" (25), but it leaves "01", which starts with a zero. So the answer is −1.

Example 2

bits="1111101" → 1

"1111101" is 125 = 5³, so a single piece is enough.

Example 3

bits="10111" → 3

Constraints

1 ≤ len(bits) ≤ 15
Every character of bits is 0 or 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table String Dynamic Programming Backtracking

Similar problems

Every Way to Space the Words Hard Keypad Words Medium All Balanced Bracket Strings Medium Cutting a Word Into Palindromes Medium Split Into Dictionary Words Medium

Input

bits="1100101"

Expected

-1

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