My assignment:
You are given a nonnegative 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 stringS
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?
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 32bit
or even 64bit
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:
0
then the number of steps is also 0
.1
then the number of steps is size
of the string.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 + (onesCount1)*2 + 1