1404.md

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

Solution 1 (time O(log(n)), space O(1))

class Solution(object):
    def numSteps(self, s):
        """
        :type s: str
        :rtype: int
        """
        ans = 0
        while s != "1":
            if s[-1] == "0":
                s = s[:-1]
                ans += 1
            else:
                ind = -1
                new_s = list(s)
                for i in range(len(new_s) - 1, -1, -1):
                    if new_s[i] == '0':
                        ind = i
                        break
                    else:
                        new_s[i] = '0'
                if ind == -1:
                    new_s = ['1'] + new_s
                else:
                    new_s[ind] = '1'
                s = "".join(new_s)
                ans += 1
        return ans