#include <iostream>
using namespace std;
class Solution {
public:
int numSteps(string s) {
int res = 0;
while(s != "1"){
if(s.back() == '1') s = addone(s);
else s = s.substr(0, s.size() - 1);
res ++;
}
return res;
}
private:
string addone(string s){
reverse(s.begin(), s.end());
s[0] += 1;
int carry = 0;
for(int i = 0; i < s.size(); i ++){
s[i] += carry;
if(s[i] == '2') s[i] = '0', carry = 1;
else carry = 0;
}
if(carry) s += '1';
reverse(s.begin(), s.end());
return s;
}
};
int main() {
cout << Solution().numSteps("1101") << endl;
cout << Solution().numSteps("10") << endl;
return 0;
}