Find the number of steps a string can be reduced to 0

Question

My assignment:

You are given a non-negative integer variable $Z$. There are two actions available that can change its value:

• if $Z$ is odd, subtract 1 from it;

• if $Z$ is even, divide it by 2.

These actions are performed until the value of $Z$ becomes 0.

You have to write a function: int solution(string &S); such that when given a string S consisting of $N$ characters containing a binary representation of the initial value of variable $Z$, returns the number of steps after which the value of $Z$ will become 0, as described above.

#include<iostream>

int solution(string &S) {
    int x = stoi(S, 0, 2);
    int count = 0;
    while (x != 0) {
        if (x % 2 == 0) {
            x /= 2;
            count++;
        } else {
            x -= 1;
            count++;
        }
    }
    return count;
}

Now the time complexity of this code blows up. Where am I going wrong in writing an efficient solution?

Answer 1

Now the time complexity of this code blows up. Where am I going wrong in writing an efficient solution?

You shouldn't convert the string into a number since it can too long to fit in a 32-bit or even 64-bit integer. Instead, what you should realise is that all we have to know is the number of 1s onesCount and the length size of the integer string (we assume there're no leading zeros as per problem statement). Let's consider an example. Let's say we have a number 11001. Then, the steps can be illustrated as below:

1 1 0 0 1   subtract rightmost bit because it's 1  
    |
    v         
1 1 0 0 0   right shift because rightmost 0  
    |
    V
0 1 1 0 0   right shift because rightmost 0 
    |
    v
0 0 1 1 0   right shift because rightmost 0 
    |
    v
0 0 0 1 1   subtract rightmost bit 1
    |
    v
0 0 0 1 0   right shift because rightmost 0 
    |
    V  
0 0 0 0 1   subtract rightmost bit 1
    |
    V
0 0 0 0 0   Complete.    

So, as you can see, if the rightmost digit is 0 (and there are still 1s to the left) then it takes one step to move to the next right digit. However, if the rightmost digit is 1 (and it's not the last one), then we need 2 steps - to nullify it and move to the next right digit. Obviously, if the leftmost digit is 1 and it's the last then it's only one step.

But then, the number of steps can be expressed as:

1. If a number is 0 then the number of steps is also 0.
2. If there's only one occurrence of 1 then the number of steps is size of the string.
3. If there're more occurrences of 1s then the total steps are onesCount * 2 + (size - onesCount - 1). But then, this is more generic than section 2 and we can use it for both cases.

Code

uint32_t solveMe(std::string &number) {
    uint32_t onesCount = std::count(number.begin(), number.end(), '1');
    if (onesCount == 0) {
        return 0;
    }

    uint32_t numberSize = number.size();

    return onesCount * 2 + (numberSize - onesCount - 1);
}

Update

As pointed out by @lucieon, another way of looking at this can be described by a formula below:

zerosCount + (onesCount-1)*2 + 1

Answer 2

Here is my solution in C#, it covers the possibilities of having leading zeros. cases such as '00011101' are covered.

public class Solution
{
    public static int EfficientCountStepsToZero(string S)
    {
        var newString = RemoveLeadingZeros(S);
        int zerosCount = 0;
        int onesCount = 0;
        for (int i = 0; i < newString.Length; i++)
        {
            if (newString[i] == '0')
            {
                zerosCount++;
            }
            else
            {
                onesCount++;
            }
        }
        return zerosCount + (onesCount - 1) * 2 + 1;
    }

    private static string RemoveLeadingZeros(string S)
    {
        char[] letter = S.ToCharArray();
        for (int i = 0; i < letter.Length; i++)
        {
            if (letter[i] == '1')
            {
                break;
            }
            letter[i] = ' ';
        }
        return new string(letter).Trim();
    }
}