Leetcode 1404. Number of Steps to Reduce a Number in Binary Representation to One
Problem Explanation
The problem is based on manipulating the binary representation of a given number, s
until we arrive at the number one (1). The rules for manipulation are simple and include:
Rule 1: If the current number is even, it must be divided by 2.
Rule 2: If the current number is odd, add 1 to it.
Our task is to calculate and return the number of steps taken to achieve this.
Approach to Solution:
The given problem can be modelled into an approach where we continuously check the last digit or the least significant bit (LSB) and accordingly apply the rules until we reach binary representation of 1.
-
If the least significant bit is '0', it means the number represented is even. As per rule, such number should be divided by 2. In binary representation, dividing by 2 is equivalent to removing the last digit. So, we simply remove the last digit and increment our steps counter.
-
If the least significant bit is '1' and it's not the only digit (number is not 1), it means the number represented is odd. As per rule, such number should be incremented by 1. In binary representation, incrementing an odd number by 1 leads to a carry propagating through all the 1's in LSB to the next 0's. So, we simulate this operation, increment our steps counter by 1 to account for the increment operation and then increment it for each 1 and corresponding 0 encountered.
-
Finally, if the binary number is '1', we can simply return the current steps counter as no more steps are needed.
To illustrate this, take the binary number '1101' as example.
- On the first iteration, the last digit (or LSB) is '1', its an odd number. We increment 1 and carry propagates through 1's to next 0. Updated binary after increment operation is '1110' and steps counter becomes 4 (1 for increment, 1 for each '1' and 2 for '0').
- On second iteration, the LSB is '0', its an even number. We divide it by 2 by removing LSB. Updated binary is '111' and steps becomes 5.
- On third iteration, the LSB is '1', it's an odd number. We increment 1 and all 1's turn to 0 and we are left with '1000'. Steps becomes 9.
- On fourth, fifth and sixth iteration, the LSB is '0', its an even number, we divide it by 2 by removing LSB and we are left with '1'. Count becomes 6.
- On seventh iteration, binary is '1' and we stop here and return the count of steps : '6'
Python Solution
1 2python 3class Solution: 4 def numSteps(self, s: str) -> int: 5 steps = 0 6 while s != '1': 7 if s[-1] == '0': 8 s = s[:-1] # removing last character or dividing by 2 9 steps += 1 10 else: 11 carry = 0 12 s_new = '' 13 for ch in reversed(s): 14 # If current bit is 1, flip it to 0 and propagate carry 15 if ch == '1': 16 s_new = '0' + s_new 17 carry = 1 18 else: 19 # If current bit is 0 and there is a carry, flip it to 1 and clear carry 20 if carry == 1: 21 s_new = '1' + s_new 22 carry = 0 23 else: 24 s_new = '0' + s_new 25 # if there is still carry left, add it to front 26 if carry == 1: 27 s_new = '1' + s_new 28 s = s_new 29 steps += 1 30 return steps
Java Solution
1 2java 3class Solution { 4 public int numSteps(String s) { 5 int steps = 0; 6 while (!s.equals("1")) { 7 if (s.charAt(s.length()-1) == '0') { 8 s = s.substring(0, s.length()-1); // removing last character or dividing by 2 9 steps += 1; 10 } else { 11 int carry = 0; 12 String s_new = ""; 13 for (int i = s.length()-1; i >= 0; --i) { 14 // If current bit is 1, flip it to 0 and propagate carry 15 if (s.charAt(i) == '1') { 16 s_new = '0' + s_new; 17 carry = 1; 18 } else { 19 // If current bit is 0 and there is a carry, flip it to 1 and clear carry 20 if (carry == 1) { 21 s_new = '1' + s_new; 22 carry = 0; 23 } else { 24 s_new = '0' + s_new; 25 } 26 } 27 } 28 // if there is still carry left, add it to front 29 if (carry == 1) { 30 s_new = '1' + s_new; 31 } 32 s = s_new; 33 steps += 1; 34 } 35 } 36 return steps; 37 } 38}
JavaScript Solution
1 2javascript 3class Solution { 4 numSteps(s) { 5 let steps = 0; 6 while (s !== '1') { 7 if (s.charAt(s.length-1) === '0') { 8 s = s.substring(0, s.length-1); // removing last character or dividing by 2 9 steps += 1; 10 } else { 11 let carry = 0; 12 let s_new = ""; 13 for (let i = s.length-1; i >= 0; --i) { 14 // If current bit is 1, flip it to 0 and propagate carry 15 if (s.charAt(i) === '1') { 16 s_new = '0' + s_new; 17 carry = 1; 18 } else { 19 // If current bit is 0 and there is a carry, flip it to 1 and clear carry 20 if (carry === 1) { 21 s_new = '1' + s_new; 22 carry = 0; 23 } else { 24 s_new = '0' + s_new; 25 } 26 } 27 } 28 // if there is still carry left, add it to front 29 if (carry === 1) { 30 s_new = '1' + s_new; 31 } 32 s = s_new; 33 steps += 1; 34 } 35 } 36 return steps; 37 } 38}
C++ Solution
1 2cpp 3class Solution { 4public: 5 int numSteps(string s) { 6 int steps = 0; 7 while (s != "1") { 8 if (s.back() == '0') { 9 s.pop_back(); // removing last character or dividing by 2 10 steps += 1; 11 } else { 12 int carry = 0; 13 string s_new = ""; 14 for (int i = s.length()-1; i >= 0; --i) { 15 // If current bit is 1, flip it to 0 and propagate carry 16 if (s[i] == '1') { 17 s_new = '0' + s_new; 18 carry = 1; 19 } else { 20 // If current bit is 0 and there is a carry, flip it to 1 and clear carry 21 if (carry == 1) { 22 s_new = '1' + s_new; 23 carry = 0; 24 } else { 25 s_new = '0' + s_new; 26 } 27 } 28 } 29 // if there is still carry left, add it to front 30 if (carry == 1) { 31 s_new = '1' + s_new; 32 } 33 s = s_new; 34 steps += 1; 35 } 36 } 37 return steps; 38 } 39};
C# Solution
1 2csharp 3using System; 4using System.Linq; 5 6public class Solution { 7 public static int NumSteps(string s) { 8 int steps = 0; 9 while (s != "1") { 10 if (s[s.Length - 1] == '0') { 11 s = s.Remove(s.Length - 1); // removing last character or dividing by 2 12 steps++; 13 } else { 14 int carry = 0; 15 string s_new = String.Empty; 16 for (int i = s.Length - 1; i >= 0; i--) { 17 // If current bit is 1, flip it to 0 and propagate carry 18 if (s[i] == '1') { 19 s_new = '0' + s_new; 20 carry = 1; 21 } else { 22 // If current bit is 0 and there is a carry, flip it to 1 and clear carry 23 if (carry == 1) { 24 s_new = '1' + s_new; 25 carry = 0; 26 } else { 27 s_new = '0' + s_new; 28 } 29 } 30 } 31 // if there is still carry left, add it to front 32 if (carry == 1) { 33 s_new = '1' + s_new; 34 } 35 s = s_new; 36 steps++; 37 } 38 } 39 return steps; 40 } 41}
Conclusions:
The problem explores the knowledge of binary arithmetic and string manipulations. The solutions are intuitive and work in O(N) time complexity with the python, java and C# solutions having a higher space complexity due to string concatenation operations. In JavaScript and C++ solutions the string concatenation operation overhead is eliminated as they do not use the '+' operator to append to string and instead they use the substring and pop_back functions respectively reducing the space complexity.
String concatenation using the '+' operator has a time complexity of O(n) which can increase execution time significantly for large inputs as new memory allocation and copying of characters is involved. However, with languages like C++ and JavaScript providing alternatives like pop_back and substring, the space overhead can be greatly reduced allowing the program to perform well even for large inputs.
In simpler terms, the key idea for this problem is to use bitwise operations to decide the next action based on whether the number is odd or even till we reach 1. Having a solid understanding of bitwise operations and how they correlate to simple arithmetic operations like division provides a basic yet effective solution to the problem.
All four solutions involve processing each bit in the binary representation and making decisions based on its value. While this is essential, how the binary representation is stored and manipulated can impact both run-time efficiency and memory usage. Therefore, when implementing such algorithms, careful consideration should be given to how best to store and manipulate data to ensure optimal performance.
Lastly, the implementation highlights that while all four languages - Python, Java, JavaScript, and C# - provide similar procedural control structures, data types and operations, the more nuanced aspects of how they handle string and memory management can lead to subtle differences in implementation and performance of the solution.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.