LeetCode 1404. Number of Steps to Reduce a Number in Binary Representation to One Solution in Java, C++, Python & More | Explanation + Code

Description

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" corresponds 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'

Solutions

Solution 1: Simulation

We simulate operations 1 and 2, while maintaining a carry carry to indicate whether there is a current carry. Initially, carry = false.

We traverse the string s from the end toward the beginning:

• If carry is true, the current bit c needs to be incremented by 1. If c is 0, it becomes 1 after adding 1, and carry becomes false; if c is 1, it becomes 0 after adding 1, and carry remains true.
• If c is 1, we need to perform operation 1, i.e., add 1, and carry becomes true.
• At this point c is 0, so we need to perform operation 2, i.e., divide by 2.

After the traversal, if carry is still true, we need to perform operation 1 one more time.

The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).

PythonJavaC++GoTypeScriptRust

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(code-box)

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; } }(code-box)

class Solution { public: int numSteps(string s) { int ans = 0; bool carry = false; for (int i = s.size() - 1; i; --i) { char 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; } };(code-box)

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 }(code-box)

function numSteps(s: string): number { let ans = 0; let carry = false; for (let i = s.length - 1; i > 0; i--) { let 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; }(code-box)

impl Solution { pub fn num_steps(s: String) -> i32 { let bytes = s.as_bytes(); let mut ans: i32 = 0; let mut carry = false; for i in (1..bytes.len()).rev() { let mut c = bytes[i]; if carry { if c == b'0' { c = b'1'; carry = false; } else { c = b'0'; } } if c == b'1' { ans += 1; carry = true; } ans += 1; } if carry { ans += 1; } ans } }(code-box)