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

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'.

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.

 

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.

 

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

 

Keep Learning!!!

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think