<p>Given the binary representation of an integer as a string <code>s</code>, return <em>the number of steps to reduce it to </em><code>1</code><em> under the following rules</em>:</p>

<ul>
	<li>
	<p>If the current number is even, you have to divide it by <code>2</code>.</p>
	</li>
	<li>
	<p>If the current number is odd, you have to add <code>1</code> to it.</p>
	</li>
</ul>

<p>It is guaranteed that you can always reach one for all test cases.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;1101&quot;
<strong>Output:</strong> 6
<strong>Explanation:</strong> &quot;1101&quot; corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14.&nbsp;
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.&nbsp; 
Step 5) 4 is even, divide by 2 and obtain 2.&nbsp;
Step 6) 2 is even, divide by 2 and obtain 1.&nbsp; 
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;10&quot;
<strong>Output:</strong> 1
<strong>Explanation:</strong> &quot;10&quot; corresponds to number 2 in their decimal representation.
Step 1) 2 is even, divide by 2 and obtain 1.&nbsp; 
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;1&quot;
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length&nbsp;&lt;= 500</code></li>
	<li><code>s</code> consists of characters &#39;0&#39; or &#39;1&#39;</li>
	<li><code>s[0] == &#39;1&#39;</code></li>
</ul>

class Solution {
public:
    void fEven(string& s, int n) {
        for(int i=n-1;i>=0;i--) {
            if(i==0) {
                s[i]='0';
                return;
            }
            s[i]=s[i-1];
        }
    }

    void fOdd(string& s, int& n) {
        int flag = 1;
        for(int i=0;i<n;i++) {
            if(s[i]=='0') {
                flag = 0;
                break;
            }
        }
        if(flag) {
            s = '1' + s;
            n++;
            for(int i=1;i<n;i++) {
                s[i]='0';
            }
            return;
        }
        
        for(int i=n-1;i>=0;i--) {
            if(s[i]=='0') {
                s[i]='1';
                return;
            }
            else {
                s[i]='0';
            }
        }
    }

    bool checkOne(string& s, int n) {
        for(int i=0;i<n-1;i++) {
            if(s[i]=='1') return false;
        }
        if(s[n-1]=='0') return false;
        return true;
    }
    
    int fSteps(string& s, int n) {
        if(checkOne(s, n)==true) return 0;

        if(s[n-1]=='1') {
            fOdd(s, n);
            return 1+fSteps(s, n);
        }
        else {
            fEven(s, n);
            return 1+fSteps(s, n);
        }
    }

    int numSteps(string s) {
        int n=s.size();
        return fSteps(s, n);
    }
};
9500