A non-negative integer variable V is given. There are two actions available that modify its value:

- if V is odd, subtract 1 from it;
- if V is even, divide it by 2.

These actions are performed until the value of V becomes 0.

For example, if V initially contains value 28, it will become 0 after seven steps:

- V contains value 28, which is even: divide by 2 and obtain 14;
- V contains value 14, which is even: divide by 2 and obtain 7;
- V contains value 7, which is odd: subtract 1 and obtain 6;
- V contains value 6, which is even: divide by 2 and obtain 3;
- V contains value 3, which is odd: subtract 1 and obtain 2;
- V contains value 2, which is even: divide by 2 and obtain 1;
- V contains value 1, which is odd: subtract 1 and obtain 0.

Write a function:

class Solution { public int solution(String S); }

that, given a zero-indexed string S consisting of N characters containing a binary representation of the initial value of variable V, returns the number of steps after which the value of V will become 0, as described above.

Assume that:

- N is an integer within the range [1..1,000,000];
- string S consists only of the characters “0” and/or “1”;
- the binary representation is big-endian, i.e. the first character of string S corresponds to the most significant bit;
- the binary representation may contain leading zeros.

For example, given string S = “011100” the function should return 7, because string S represents the number 28 and 28 becomes 0 after seven steps, as explained above.

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(1) (not counting the storage required for input arguments).

1 2 3 4 5 6 7 8 9 10 11 12 13 |
def solution(num): num = int(num, 2) count = 0 while num != 0: if num % 2 == 0: num = num / 2 count = count + 1 else: num = num - 1 count = count + 1 return count print(solution('011100')) |