Given a binary string representing a positive integer, count how many operations are needed to reduce it to 1 using the standard divide-by-2 and plus-one rules.
Problem
You are given a binary string s representing a positive integer with no leading zeros.
In one step, you can perform the following operation on the current number:
- If the number is even, divide it by
2. - If the number is odd and greater than
1, add1to it.
Return the number of steps required to reduce the number to 1.
The key challenge is that the number may be very large, so you should reason directly from its binary representation instead of converting it to an integer type that may overflow.
Input Format
- A binary string
s. scontains only'0'and'1'.srepresents a positive integer without leading zeros.
Output Format
- Return a single integer: the number of operations needed to transform the value of
sinto1.
Constraints
1 <= |s|sis a valid binary representation of a positive integer.- The answer fits in a 32-bit signed integer for the intended test range.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.