# Codility challenge: Minimum number of steps to reduce number to 1

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).
{"ft_lang_label":"__label__en","ft_lang_prob":0.9004296,"math_prob":0.98115593,"size":1890,"snap":"2021-21-2021-25","text_gpt3_token_len":517,"char_repetition_ratio":0.14634146,"word_repetition_ratio":0.07520892,"special_character_ratio":0.30476192,"punctuation_ratio":0.15158924,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99780416,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-05-13T19:08:08Z\",\"WARC-Record-ID\":\"<urn:uuid:d35b51d2-d61a-47e4-bcea-40902afed437>\",\"Content-Length\":\"30226\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:417c7609-0d8b-4f6a-a931-ddb15b7b1006>\",\"WARC-Concurrent-To\":\"<urn:uuid:1a2bfbf8-d0e4-4d0e-a9c5-47541caacaf3>\",\"WARC-IP-Address\":\"209.222.96.146\",\"WARC-Target-URI\":\"https://luciekimotho.com/blog/codility-challenge-minimum-number-of-steps-to-reduce-number-to-1/\",\"WARC-Payload-Digest\":\"sha1:CXDJMRKLGBQVZ6QOJIYSH2XWIIUAJ37R\",\"WARC-Block-Digest\":\"sha1:LCDO7KEBP6GHZBOKOQ2237XS235J5AKA\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-21/CC-MAIN-2021-21_segments_1620243991943.36_warc_CC-MAIN-20210513173321-20210513203321-00086.warc.gz\"}"}