# 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:

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

## 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

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 numberpublic 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!!!**

Comments

## No comments yet

## Be the first to share what you think