typedeftemplate's blog

Minimum number of operations to get from one number to another
By typedeftemplate, history, 5 years ago, In English

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.

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Dynamic programming would definitely work. Initialize an array $$$dp$$$ to $$$\infty$$$, convert the string to an integer $$$n$$$, and run the following process:

dp[n] = 0
for i = n to 0, descending
  if (i is divisible by 2) dp[i / 2] = min(dp[i / 2], dp[i] + 1) // one operation, divide by two
  if (i > 0) dp[i - 1] = min(dp[i - 1], dp[i] + 1) // one operation, subtract one

The answer is $$$dp[0]$$$. Any $$$dp[i]$$$ stores the minimum number of operations to get to $$$i$$$, which is equivalent to $$$1 + min(dp[2 * i], dp[i + 1])$$$ since those are the only two numbers $$$i$$$ can come from. This is $$$O(n)$$$.

Also, in what case does the greedy (divide until you have a 1 on the right, then subtract 1, then repeat) strategy fail? The countercase offered in the StackOverflow doesn't apply to this problem, because you can't add.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    Oh wow. Thanks for your reply. I actually just read the Stack Overflow post, and I saw them mention that greedy didn't work. I didn't even realize they were adding 1. In that case, do you even need DP? Could you just be greedy? Also, wouldn't the DP solution you provided get MLE (memory limit exceeded) since N = 1,000,000?

    But I guess you can just be greedy anyways, so it doesn't matter?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      I'm not good at proofs, but the greedy just intuitively seems correct (if your last digit is a $$$1$$$, you have to subtract, and if it's a $$$0$$$, then use the logic of the StackOverflow, and also division reduces the number way more than subtraction).

      Also, I don't know the environment of that programming contest, but in most OJ's, this won't come too close to MLE. $$$10^6$$$ 4-bit integers is less than 4 megabytes, and the MLE of (for example) a standard CF problem is 256 megabytes.

      edit: To actually answer your question, yes, greedy would way outperform DP and be the best solution to use.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        You always subtract 1 from odd numbers, and always divide even numbers by 2? Why it works?

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I'll try to formalize my intuition.

          If the number is odd, it is not divisible by 2, so you can't divide and therefore have to subtract.

          If the number is even, you can do either type of operation. Let's say you subtract 1 from the number. Then, you end up with an odd number, meaning you have to subtract again. You've now subtracted 2 from the total number. In any case of an even number, if you want to subtract, you always have to subtract an even number to be able to divide again. If you're never going to divide again, then the answer is $$$O(1)$$$ and trivial (so you can check the case of only subtracting at every step)

          Otherwise, say you divide by 2, and before that, you subtracted an even $$$x$$$ from the number. You could obtain this exact number by instead dividing beforehand and performing $$$\frac{x}{2}$$$ subtractions. For any even (positive) $$$x$$$, $$$\frac{x}{2} + 1$$$ < $$$x + 1$$$, so it is always more optimal to divide.

          → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think i got a solution for this...

include<bits/stdc++.h>

using namespace std;

int main() { string s; cin>>s; int start=0; while(s[start]!='1') start++;

int end=s.length()-1; int op=0; while(start<=end) { if(s[end]=='1') { s[end]='0'; } else end--; op++; } cout<<op-1; return 0; }

→ Reply