Skip to main content
Talentd

Number of Steps to Reduce a Number in Binary Representation to One - Solution & Explanation

MediumStringBit Manipulation18 min readAsked at: Amazon, Microsoft, Meta +4
Practice this problem

Problem Statement

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'

Approach Overview

Problem Overview: A binary string represents a positive integer. Apply two rules until the number becomes 1: if the number is even, divide it by 2; if odd, add 1. The task is to count how many operations are required.

Approach 1: Simulation Based on Binary Operations (O(n) time, O(1) space)

Treat the input as a binary string and simulate the operations directly without converting it to an integer. Iterate from the rightmost bit toward the left while maintaining a carry that represents previous +1 operations. When the current bit plus carry is even, the operation is a divide-by-2 (move left). When it is odd, an add-1 occurs, which creates a carry and requires an extra step. Each bit is processed once, so the algorithm runs in O(n) time with constant extra space. This approach leverages simple rules of bit manipulation and avoids expensive large-number arithmetic.

The key insight: adding 1 to a binary number may propagate a carry through consecutive 1s. Instead of modifying the entire string repeatedly, track that carry logically while scanning. Every bit contributes either one step (division) or two steps (add then divide) depending on its effective value after carry.

Approach 2: Decimal Conversion and Simulation (O(n^2) time, O(n) space)

Convert the binary string to a decimal integer and simulate the rules directly: if the number is even, divide by 2; otherwise add 1. Repeat until the value becomes 1 while counting operations. The logic is straightforward and mirrors the problem statement exactly.

This method is easy to implement in languages with built-in big integers, but the integer can grow beyond standard limits. Each arithmetic operation on large numbers costs more than constant time, so the overall complexity becomes roughly O(n^2) where n is the binary length. The approach also uses O(n) space for the big integer representation. It relies more on numeric conversion than direct string processing.

Recommended for interviews: The binary simulation approach. Interviewers expect you to reason about binary behavior and carries instead of converting to decimal. Implementing the right-to-left scan shows strong understanding of binary arithmetic and keeps the complexity optimal at O(n) time with O(1) space.

Approach 1: Approach 1: Simulation Based on Binary Operations

This approach involves simulating the reduction steps performed directly on the binary number string. We traverse the binary string backwards, simulating each step based on whether the current number is odd or even. Additionally, whenever we encounter a carry after incrementing an odd number, we propagate the carry to handle the necessary binary addition.

This Python function iterates through the binary string from the least significant bit towards the most significant bit. It checks the parity of the current digit plus any existing carry. If the sum is even, this implies the number is even and a division takes place (1 step). If the sum is odd, an addition and subsequent division occur (2 steps). The carry represents binary addition's overflow, simulating the bit handling required.

Code

PythonC++C#JavaJavaScriptC

Python

C++

C#

Java

JavaScript

C

Complexity

Time Complexity: O(n), where n is the length of the string s.
Space Complexity: O(1), only a constant amount of extra space is used.

Try this approach in the editor →

Approach 2: Approach 2: Decimal Conversion and Simulation

Convert the binary representation to a decimal integer, then simulate the operations using intuitive arithmetic operations. This approach avoids character-level string manipulations.

This implementation converts the binary input to a decimal integer using Python's base conversion. Then the function reduces the number using arithmetic operations analogous to the original rules (dividing when even or incrementing plus dividing when odd).

Code

PythonC++C#JavaJavaScriptC

Python

C++

C#

Java

JavaScript

C

Complexity

Time Complexity: O(n) for initial conversion, O(log m) for operations (where m is the integer value).
Space Complexity: O(1), after input conversion.

Try this approach in the editor →

Approach 3: Simulation

We simulate operations 1 and 2, while maintaining a carry carry to indicate whether there is a current carry. Initially, carry = false.

We traverse the string s from the end toward the beginning:

  • If carry is true, the current bit c needs to be incremented by 1. If c is 0, it becomes 1 after adding 1, and carry becomes false; if c is 1, it becomes 0 after adding 1, and carry remains true.
  • If c is 1, we need to perform operation 1, i.e., add 1, and carry becomes true.
  • At this point c is 0, so we need to perform operation 2, i.e., divide by 2.

After the traversal, if carry is still true, we need to perform operation 1 one more time.

The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Simulation Based on Binary Operations

Time Complexity: O(n), where n is the length of the string s.
Space Complexity: O(1), only a constant amount of extra space is used.

Approach 2: Decimal Conversion and Simulation

Time Complexity: O(n) for initial conversion, O(log m) for operations (where m is the integer value).
Space Complexity: O(1), after input conversion.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simulation Based on Binary OperationsO(n)O(1)Best general solution. Efficient for very long binary strings and commonly expected in interviews.
Decimal Conversion and SimulationO(n^2)O(n)Quick to implement when big integers are available and input size is small.

Video Solution

Number of Steps to Reduce a Number in Binary Representation to One | 2 Approaches | Leetcode 1404 • codestorywithMIK • 13,587 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Steps to Reduce a Number in Binary Representation to One easy or hard?
The problem is typically classified as Medium. The rules are simple, but recognizing that you can simulate binary operations with a carry instead of converting to decimal is the key insight that makes the optimal O(n) solution possible.
Number of Steps to Reduce a Number in Binary Representation to One Python/Java solution
In Python or Java, implement a right-to-left scan of the binary string and track a carry from previous add operations. Increment the step counter based on whether the effective bit is odd or even. The logic is identical across languages and runs in O(n) time with constant space.
How to solve Number of Steps to Reduce a Number in Binary Representation to One in O(n)?
Iterate from the least significant bit toward the most significant bit and maintain a carry value. If the current bit plus carry is even, count one step for division by 2. If it is odd, count two steps: one for adding 1 and another for division. Continue until reaching the leading bit, giving an O(n) solution.
What is the best approach for Number of Steps to Reduce a Number in Binary Representation to One?
The optimal approach simulates the operations directly on the binary string while scanning from right to left and tracking a carry. Each bit determines whether an add‑1 and divide‑by‑2 are required. This method runs in O(n) time and O(1) space because each bit is processed once.
Is Number of Steps to Reduce a Number in Binary Representation to One asked at Google/Amazon/Meta?
Problems involving binary operations, carries, and bit manipulation appear frequently in interviews at companies like Amazon, Google, and Meta. This problem tests understanding of binary arithmetic and efficient simulation, which are common themes in technical interviews.
What data structure is used in Number of Steps to Reduce a Number in Binary Representation to One?
The primary structure is a string representing the binary number. The optimal solution processes the string with simple counters and a carry variable, relying on bit manipulation concepts rather than additional data structures.
What is the time complexity of Number of Steps to Reduce a Number in Binary Representation to One?
The optimal binary simulation approach runs in O(n) time where n is the length of the binary string, with O(1) extra space. A simpler approach that converts the binary string to a big integer and repeatedly applies the operations typically costs about O(n^2) due to large-number arithmetic.

Ready to solve this problem?

Practice Number of Steps to Reduce a Number in Binary Representation to One with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Moves to Reach Target Score