python

You are given a string S of length N which encodes a non-negative number V in a binary form. Two types of operations may be performed on it to modify its value: if Vis odd, subtract 1 from it; . if Vis even, divide it by 2. These operations are performed until the value of V becomes 0. For example, if string S = "011100", its value V initially is 28. The value of V would change as follows: V = 28, which is even: divide by 2 to obtain 14, V = 14, which is even: divide by 2 to obtain 7. V = 7, which is odd: subtract 1 to obtain 6; V = 6, which is even: divide by 2 to obtain 3; V = 3, which is odd: subtract 1 to obtain 2: V = 2, which is even: divide by 2 to obtain 1: V = 1, which is odd: subtract 1 to obtain 0. Seven operations were required to reduce the value of V to O. Write a function: det solution () that, given a string S consisting of N characters containing a binary representation of the initial value V, returns the number of operations after which its value will become o. Examples 1. Given S = "011100", the function should return 7. String S represents the numbe 28, which becomes after seven operations, as explained above. 2. Given S = "111", the function should return 5. String Sencodes the number V = Its value will change over the following five operations: V = 7, which is odd: subtract 1 to obtain 6; V = 6, which is even: divide by 2 to obtain 3. V = 3, which is odd: subtract 1 to obtain 2, V = 2, which is even: divide by 2 to obtain 1; V = 1, which is odd: subtract 1 to obtain 0. 3. Given S = "1111010101111', the function should return 22. 4. Given string S consisting of "1" repeated 400,000 times, the function should return 799,999. Write an efficient algorithm for the following assumptions: string S consists only of the characters 'O' and/or '1' N, which is the length of string S, is an integer within the range [1..1,000,000): the binary representation is big-endian, i.e. the first character of string Scorresponds to the most significant bit; the binary representation may contain leading zeros