c++stltime-complexityc++14complexity-theory

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

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?

Solution

• 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 `1`s `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 `1`s 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 `1`s 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
``````