Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
How to solve this problem?
4.
Approach: Efficient 
4.1.
Algorithm
5.
Implementation
5.1.
A different version:
6.
Analysis of Complexity
7.
FAQ's
8.
Key Takeaways
Last Updated: Mar 27, 2024

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

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Today's problem, i.e., the number of steps to reduce a number in binary representation to one, is one of the vital problems of the topic binary string.

We will get into all the methods to solve this problem.

 

Without any further delays, let's move to our problem statement.

Problem Statement

We will be given the binary representation of the integer as string str; we have to return the number of steps to reduce the given integer to 1. To solve this particular problem, there are specific rules:

 

  1. If the current number is even, then you have to divide it by '2'.
  2. If the current number is odd, then you have to add 1 to it.

 

After following these rules we will get the total number of steps to reduce a number.

Let's see the below example for better understanding.

 

Input: str = “1111”

Output: 5

Explanation:

"1111" corresponds to 15, which is an odd number, and according to the rule, when the current number is odd, we have to add '1' to it.

 

  1. 15 is odd. add '1' to 15; it will be '16'.
  2. '16' is even, divided by 2. it will be '8'.
  3. '8' is even, divided by 2; it will be '4'.
  4. '4' is even, divided by 2. it will be '2'.
  5. '2' is even, divided by 2; it will be '1'.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

How to solve this problem?

  1. For every step, we need to find out that the string is even or odd.
  2. Read the string from right to left.
  3. If the string ends with '0', the number is even; otherwise, it is odd.
  4. We will be stimulating the rules of the problem.

If you have understood the problem statement, let's move towards the approach.

Approach: Efficient 

Algorithm

  1. Initialize carry=0 and ret=0.
  2. Except for the initial digit, we iterate the characters of a binary string from the end to the beginning, I = [n-1..1].
  3. We require two operations if str[i] + carry == 1 -> It's an odd number: add ‘1’ and divide by two, ret+=2.
  4. If str[i] + carry == 0, then We only need one operation because it's an even number: ret+= 1 if you divide by two.
  5. Finally, if carry = 1, total = s[0] + carry = 2 requires one additional operation to divide by 2 in order to become one, else if carry = 0 then total = s[0] + carry = 1 requires no further operation.
  6. So the result is ret + carry.
  7. This is how you can calculate the number of steps to reduce a number to one.

 

Implementation

class Solution {

    //method to find the number of steps to reduce a number                   
    public int steps(String s) {
        int n = s.length();

        //intializing carry as '0' to keep an update 
        //about the even or odd number
        int carry = 0;
        
        //To store the final answer
        int ret= 0;
        
        i = n-1;
        //For iterating over the string
        while(i>0)
        {
            
            // curr digit + carry is '1'; need to extra adding '1' operation;
            if (s.charAt(i--) - '0' + carry == 1) { 
                ret++;
                carry = 1;
            }
            ret++; // dividing 2;
        }

          return ret + carry;
    }
  public static void main(String args[])
  {                
      String s;
      s = "1111";

System.out.println(steps(s));
    }  
}

Output

5

 

A different version:

 

//number of steps to reduce a number
public int numSteps(String s) {

        int n = s.length(), res = 0, i = n - 1, carry = 0;
        char[] arr = s.toCharArray();

        while (i > 0) {
            if (carry == 1 && arr[i] == '0' || carry == 0 && arr[i] == '1') {
                res += 2;
                carry = 1;
            }

            else if (arr[i] == '0' && carry == 0) {
                res++;
            } else {
                res++;
                carry = 1;
            }
            i--;
        }

        if (carry > 0
          res++;

        return res;
    }

 

Analysis of Complexity

 

Time Complexity: The time complexity to count the number of steps to reduce a number is O(n). This is the most efficient way to solve this problem.

 

Space Complexity: Space complexity to solve this problem is O(1), as no extra space is required.

Also see, Euclid GCD Algorithm

FAQ's

 

What do you mean by a number of steps to reduce a number in binary representation to one?

Answer: In this problem, we have to find out the minimum number of steps to reduce a number to 1, which is given in the form of a binary number.

 

Is there any other approach to count the number of steps to reduce a number to one?

Answer: This is the most appropriate and straightforward approach to solve this problem. There can be many ways; one way is by using BigInteger in Java.

 

Does this problem require string operations?

Answer: No, This approach doesn't require the use of string operations.

 

Key Takeaways

 

So, the idea to solve this problem is to count the number of steps to reduce a number by following the rules. For better understanding, we have written the code in Java.

 

If the idea of the problem is sorted in your mind, you can jump on to solve the Number Of Steps and get it accepted.
Check out this problem - Longest String Chain

 

You can also visit our Interview experiences to shine your skills.

 

Keep Learning!!!

 

Previous article
Gray Code
Next article
Divide Two Integers
Live masterclass