This was a question I was asked in a programming contest at a local college, which I was not able to solve. I was wondering whether anyone knows the way to solve it:

Given a string S consisting only of binary digits (e.g. we can have S = "10101"), what's the minimum number of operations you need to perform to get from S to 0? There are two valid operations that can be performed:

1) Divide by 2 2) Subtract by 1.

For example, if the string S is "011100," which has decimal representation 28, then you can go 28->14->7->6->3->2->1->0, which requires 7 operations. Since this is optimal, the answer is 7.

I tried implementing the greedy solution, which does not work. A very similar problem is here: https://stackoverflow.com/questions/39588554/minimum-number-of-steps-to-reduce-number-to-1

The number that S was representing would be at most 1,000,000, which means that S has around 20 digits max. Maybe there's an even quicker way to do it, without converting it to an integer first?

However, I was only given the binary representation of the number as a string, and I wasn't given the number itself. So I don't quite think that the technique described in the post is enough.

Also, I have to reduce to 0, whereas the post wanted to reduce to 1. I would greatly appreciate some help. As of now, I think the problem might require dynamic programming, which I am not so great with.