Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1404.html

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

Given a number s in their binary representation. 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's guaranteed that you can always reach to one for all testcases.

 

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'

Related Topics:
String, Bit Manipulation

Solution 1.

• Java
• C++
• Python
• Go

• class Solution {
      public int numSteps(String s) {
          int steps = 0;
          StringBuffer sb = new StringBuffer(s);
          while (sb.length() > 1) {
              char lastChar = sb.charAt(sb.length() - 1);
              if (lastChar == '0')
                  sb.deleteCharAt(sb.length() - 1);
              else
                  sb = addOne(sb);
              steps++;
          }
          return steps;
      }
  
      public StringBuffer addOne(StringBuffer sb) {
          int length = sb.length();
          int lastZeroIndex = -1;
          for (int i = length - 1; i >= 0; i--) {
              if (sb.charAt(i) == '0') {
                  lastZeroIndex = i;
                  break;
              }
          }
          if (lastZeroIndex < 0) {
              for (int i = length - 1; i >= 0; i--)
                  sb.setCharAt(i, '0');
              sb.insert(0, '1');
          } else {
              sb.setCharAt(lastZeroIndex, '1');
              for (int i = lastZeroIndex + 1; i < length; i++)
                  sb.setCharAt(i, '0');
          }
          return sb;
      }
  }
  
  ############
  
  class Solution {
      public int numSteps(String s) {
          boolean carry = false;
          int ans = 0;
          for (int i = s.length() - 1; i > 0; --i) {
              char c = s.charAt(i);
              if (carry) {
                  if (c == '0') {
                      c = '1';
                      carry = false;
                  } else {
                      c = '0';
                  }
              }
              if (c == '1') {
                  ++ans;
                  carry = true;
              }
              ++ans;
          }
          if (carry) {
              ++ans;
          }
          return ans;
      }
  }
  

• // OJ: https://leetcode.com/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one/
  // Time: O(N)
  // Space: O(1)
  class Solution {
  public:
      int numSteps(string s) {
          int ans = 0;
          while (s != "1") {
              if (s.back() == '1') {
                  int i = s.size() - 1;
                  while (i >= 0 && s[i] == '1') {
                      s[i] = '0';
                      --i;
                  }
                  if (i == -1) s.insert(s.begin(), '1');
                  else s[i] = '1';
              } else s.pop_back();
              ++ans;
          }
          return ans;
      }
  };
  

• class Solution:
      def numSteps(self, s: str) -> int:
          carry = False
          ans = 0
          for c in s[:0:-1]:
              if carry:
                  if c == '0':
                      c = '1'
                      carry = False
                  else:
                      c = '0'
              if c == '1':
                  ans += 1
                  carry = True
              ans += 1
          if carry:
              ans += 1
          return ans
  
  ############
  
  class Solution:
      def numSteps(self, s: str) -> int:
          step = 0
          s_int = int(s, 2)
          while s_int != 1:
              if s_int % 2 == 0:
                  s_int //= 2
              else:
                  s_int += 1
              step += 1
          return step
  

• func numSteps(s string) int {
  	ans := 0
  	carry := false
  	for i := len(s) - 1; i > 0; i-- {
  		c := s[i]
  		if carry {
  			if c == '0' {
  				c = '1'
  				carry = false
  			} else {
  				c = '0'
  			}
  		}
  		if c == '1' {
  			ans++
  			carry = true
  		}
  		ans++
  	}
  	if carry {
  		ans++
  	}
  	return ans
  }
  

All Problems

All Solutions