• Posts

Problem 1404 Number of Steps to Reduce a Number in Binary Representation to One

Problem Statement

Link - Problem 1404

Question

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'

Solution

class Solution {
public:
    int numSteps(string s) {
        int ans = 0, i = s.size()-1;
        while(i>=0)
        {
            if(s[i]=='0')
            {
                ans++;i--;
                continue;
            }
            else if(i==0)
            {
                return ans;
            }
            else
            {

                while(i>=0 && s[i]=='1')
                {
                    ans++;i--;
                }
                if(i>=0)
                {
                    s[i]='1';
                }
                ans++;
            }
        }

        return ans;
    }
};

Complexity Analysis

| Algorithm         | Time Complexity | Space Complexity |
| ----------------- | --------------- | ---------------- |
| Carry propagation | O(n)            | O(1)             |

Explanation

Intial Thoughts

To approach this problem, consider the binary representation of a number as a sequence of operations. The goal is to reach ‘1’ in the fewest steps possible. Think of it like navigating through a maze, where each step is either a division by 2 (if the current number is even) or an addition of 1 (if the current number is odd). The key is to understand the impact of these operations on the binary representation of the number. Consider breaking down the problem into smaller parts, focusing on the rightmost bits of the binary representation first. Also, note that the problem guarantees that it’s always possible to reach ‘1’ for all test cases, so the focus should be on minimizing the number of steps required.

Intuitive Analysis

Intuitively, solving this problem involves understanding the pattern of operations required to reduce a binary number to ‘1’. One approach is to think of the process as a series of ‘carries’ in the binary representation. When a ‘1’ bit is encountered in the middle of the sequence, it triggers a chain reaction of ‘carries’ that need to be propagated to the left until a ‘0’ is found. This process can be seen as a sequence of additions and divisions that gradually reduce the number. Another useful intuition is to recognize that the number of steps required is closely related to the number of ‘1’ bits in the binary representation, especially those that are not at the very right. By understanding how these ‘1’ bits affect the sequence of operations, it’s possible to develop an efficient strategy for minimizing the number of steps.

1. Intuition

• The problem requires reducing a binary number to 1 by either dividing it by 2 if it’s even or adding 1 if it’s odd.
• The key insight is to process the binary string from right to left, as this allows us to easily determine whether the current number is even or odd.
• When encountering a ‘0’ in the binary string, we can simply increment the step count and move to the next digit.
• When encountering a ‘1’, we need to add 1 to the number, which can cause a carry to the next digit.
• The solution works by maintaining a running count of steps and iterating through the binary string from right to left.
• The time complexity of this solution is O(n), where n is the length of the binary string.
• The space complexity is O(1), as we only use a constant amount of space to store the step count and the current index.

2. Implementation

• The numSteps function takes a binary string s as input and initializes the step count ans to 0 and the index i to the last character of the string.
• The function uses a while loop to iterate through the binary string from right to left, checking each character to determine whether to increment the step count or add 1 to the number.
• When a ‘0’ is encountered, the step count is incremented and the index is decremented using ans++ and i--.
• When a ‘1’ is encountered, the function checks if it’s the most significant bit using i == 0, and if so, returns the step count.
• If the current bit is ‘1’ and it’s not the most significant bit, the function increments the step count and decrements the index until it finds a ‘0’ using a nested while loop.
• Once a ‘0’ is found, the function sets the corresponding bit to ‘1’ using s[i] = '1' and increments the step count using ans++.
• The function returns the total step count ans after iterating through the entire binary string.

Complexity Analysis

Time Complexity:

• The algorithm iterates through the input string s once, with a while loop that runs from i = s.size()-1 to i = 0, resulting in a linear number of operations proportional to the size of the input, thus O(n).
• The dominant operation is the while loop, which scans the string s and performs a constant amount of work for each character, leading to a time complexity of O(n).
• The time complexity is justified as O(n) because the algorithm visits each character in the string at most once, with no nested loops or recursive calls that would increase the time complexity beyond linear.

Space Complexity:

• The algorithm only uses a constant amount of extra memory to store the variables ans and i, regardless of the size of the input string s.
• The input string s is modified in-place, so no additional data structures are allocated that scale with the input size, resulting in a space complexity of O(1).
• The space complexity is justified as O(1) because the algorithm does not allocate any data structures that grow with the size of the input, using only a fixed amount of memory to store the variables.

Footnote

This question is rated as Medium difficulty.

Hints

Read the string from right to left, if the string ends in ‘0’ then the number is even otherwise it is odd.

Simulate the steps described in the binary string.

Similar Questions: