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:

If the current number is even, then you have to divide it by '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.

15 is odd. add '1' to 15; it will be '16'.

'16' is even, divided by 2. it will be '8'.

'8' is even, divided by 2; it will be '4'.

'4' is even, divided by 2. it will be '2'.

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

For every step, we need to find out that the string is even or odd.

Read the string from right to left.

If the string ends with '0', the number is even; otherwise, it is odd.

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

Initialize carry=0 and ret=0.

Except for the initial digit, we iterate the characters of a binary string from the end to the beginning, I = [n-1..1].

We require two operations if str[i] + carry == 1 -> It's an odd number: add ‘1’ and divide by two, ret+=2.

If str[i] + carry == 0, then We only need one operation because it's an even number: ret+= 1 if you divide by two.

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.

So the result is ret + carry.

This is how you can calculate the number of steps to reduce a number to one.

Implementation

classSolution {

//method to find the number of steps to reduce a number publicintsteps(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; } publicstaticvoidmain(String args[]) { String s; s = "1111";

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

Output

5

A different version:

//number of steps to reduce a number publicintnumSteps(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; }

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