Problem statement

https://binarysearch.com/problems/Reduce-Binary-Number-to-One/

Solution

We can simulate the process with stack: first remove zeros from the end. Next on each step remove ones and increase previous element.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s):
        ans = 0
        stack = [int(i) for i in s]
        while stack[-1] == 0:
            ans += 1
            stack.pop()
        
        if stack == [1]: return ans
        while len(stack) > 1:
            while stack and stack[-1] == 1:
                stack.pop()
                ans += 1
            if stack:
                stack[-1] += 1
                ans += 1
            else:
                break

        return ans + 1