DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

1 1

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.

Example 1:

Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14. 
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4. 
Step 5) 4 is even, divide by 2 and obtain 2. 
Step 6) 2 is even, divide by 2 and obtain 1. 

Example 2:

Input: s = "10"
Output: 1
Explanation: "10" corressponds to number 2 in their decimal representation.
Step 1) 2 is even, divide by 2 and obtain 1. 

Example 3:

Input: s = "1"
Output: 0

Constraints:

  • 1 <= s.length <= 500
  • s consists of characters '0' or '1'
  • s[0] == '1'

SOLUTION:

class Solution:
    def numSteps(self, s: str) -> int:
        steps = 0
        while s != "1":
            if s[-1] == "0":
                s = s[:-1]
            else:
                i = len(s) - 1
                carry = 1
                while carry > 0 and i >= 0:
                    curr = int(s[i]) + carry
                    s = s[:i] + str(curr % 2) + s[i+1:]
                    carry = curr // 2
                    i -= 1
                if carry > 0:
                    s = "1" + s
            steps += 1
        return steps
Enter fullscreen mode Exit fullscreen mode

AWS Security LIVE!

Join us for AWS Security LIVE!

Discover the future of cloud security. Tune in live for trends, tips, and solutions from AWS and AWS Partners.

Learn More

Top comments (0)