Time Cost

32min41s

Implementation

Bit Manipulation. Solution 1 provides an intuitive appraoch to solve this problem. Solution 2 is an optimized version. We use greedy + bit manipulation. Using a carry variable to identify if there’s a carry value from low-bits.

Code

• Solution 1

  class Solution {
  public:
    int numSteps(string s) {
        // note that if n is 2^x, then it will directly divide continuously to 1
        s = '0' + s;
        int steps = 0;
        int right = s.length()-1;
        int popcount = 0;
  
        for (int i=0; i<s.length(); i++) {
            if (s[i] == '1') popcount++;
        }
  
        // stops until there remains one 1-bit
        while (popcount > 1) {
            if (s[right] == '0') {
                s = s.substr(0, s.length()-1);
                right = (int)s.length() - 1;
            }else{
                // continues reading left until encounters 0-bit
                // 010011 -> 010100
                int left = right;
                while (left >= 0) {
                    if (s[left] == '1') {
                        s[left] = '0';
                        popcount--;
                    }else{
                        // stops
                        s[left] = '1';
                        popcount++;
                        break;
                    }
                    left--;
                }
            }
            steps++;
        }
  
        for (int i=s.length()-1; i>=0; i--) {
            if (s[i] == '1') {
                steps += (s.length()-1 - i);
                break;
            }
        }
          
        return steps;
    }
  };
  

• Solution 2

  class Solution {
  public:
    int numSteps(string s) {
        int steps = 0, carry = 0;
        for (int i = s.length() - 1; i > 0; i--) {
            int bit = s[i] & 1;
            steps += 1 + (bit ^ carry);
            carry |= bit;
        }
        return steps + carry;
    }
  };