โ† Google questions

Binary String Split

Filed under Google

Free read 2 of 3

Generate powers of 5 and convert them to binary strings.

The question

Split a binary string into the minimum number of substrings such that each substring is a binary representation of a power of 5 (e.g., 5^0=1, 5^1=5(101), 5^2=25(11001)).

Constraints

  • String length up to 1000
  • Return -1 if no valid split exists

Examples

Input
s = '101101'
Output
2
Why
'101' is 5, '101' is 5. Total 2 parts.

Approach

  1. Generate powers of 5 and convert them to binary strings.

Tips

  • What they are testing: Tests dynamic programming or greedy approach with backtracking.
  • Common mistake: Assuming a greedy approach works without verifying if the remainder can be split.

Related Google questions

Collected from public candidate posts and coding forums. Updated Nov 2026.