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"))
|