aboutsummaryrefslogtreecommitdiff
path: root/num_steps_reduct_num.py
diff options
context:
space:
mode:
Diffstat (limited to 'num_steps_reduct_num.py')
-rw-r--r--num_steps_reduct_num.py32
1 files changed, 32 insertions, 0 deletions
diff --git a/num_steps_reduct_num.py b/num_steps_reduct_num.py
new file mode 100644
index 0000000..6ff4efc
--- /dev/null
+++ b/num_steps_reduct_num.py
@@ -0,0 +1,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"))