1404. Number of Steps to Reduce a Number in Binary Representation to One

simulation

T: O(n^2) , need string move index

S: O(n)

class Solution {
    public int numSteps(String s) {
        if (s.length() == 1) {
            return 0;
        }
        int count = 0;
        StringBuilder sb = new StringBuilder(s);
        while (sb.length() > 1) {
            if (sb.charAt(sb.length()-1) == '1') { 
                StringBuilder newSb = new StringBuilder();
                newSb.append('0'); 
                boolean carry = true;
                for (int i = sb.length()-2; i >= 0; i--) {
                    if (carry) {
                        if (sb.charAt(i) == '1') {
                            newSb.append('0'); 
                            carry = true;
                        } else {
                            newSb.append('1'); 
                            carry = false;
                        }
                    } else {
                        newSb.append(sb.charAt(i)); 
                        carry = false;
                    }
                }
                if (carry) {
                    newSb.append('1'); // 001
                }
                sb = newSb.reverse(); // 100
            } else {
                sb.deleteCharAt(sb.length()-1);
            }
            count++;
        }
        return count;
    }
}

/**

11 
 1
100

1
 */

T: O(n)

S: O(1)

class Solution {
    public int numSteps(String s) {
        int n = s.length();
        int carry = 0;
        int count = 0;
        for (int i = n-1; i > 0; i--) { // remain last digit, goal is to have last 1
            int curNum = (s.charAt(i) - '0') + carry;
            //System.out.println(curNum);
            if (curNum % 2 == 1) {
                count += 2;
                carry = 1;
            } else {
                count++;
            }
        }
        if (carry == 1) {  // means there still one more even digit need to handle, so add 1 (if carry is 1)
            count++; // at last, only left 1, but carry is 1 -> means become 10 -> one more even digit (0) need to add count
        }
        return count;
    }
}
/**
1101
 1
 122
   
 */