aboutsummaryrefslogtreecommitdiff
path: root/num_steps_reduct_num.py
blob: 6ff4efc56f6979537f941a7b6e7215b44562bd06 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 1404. Number of Steps to Reduce a Number in Binary Representation to One

"""
given the binary representation of an integer as a string 's', return the
number of steps to reduce it to 1 under the following rules. if the current
number is even, you have to divide it by 2. if the current number is odd, you
have to add 1 to it. it is guaranteed that you can always reach one for all
test cases.
"""


class Solution(object):
    def numSteps(self, s):
        """
        :type s: str
        :rtype: int
        """
        ans, carry, n = 0, 0, len(s)
        for i in range(n - 1, 0, -1):
            if int(s[i]) + carry == 1:
                carry = 1
                ans += 2
            else:
                ans += 1
        return ans + carry


if __name__ == "__main__":
    obj = Solution()
    print(obj.numSteps("1101"))
    print(obj.numSteps("10"))
    print(obj.numSteps("1"))