Number of Steps to Reduce a Number in Binary Representation to One
Number of Steps to Reduce a Number in Binary Representation to One solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Number of Steps to Reduce a Number in Binary Representation to One is a medium coding problem on strings, bit manipulation and simulation, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Bit Manipulation, Simulation
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the binary representation of an integer as a string s.
Reduce it to 1 using these steps:
- If the number is even, divide it by 2.
- If it is odd, add 1 to it.
Return the number of steps required. The input is guaranteed to have no leading zeros other than the number "1" itself.
Example 1
Input: s = "1101"
Output: 6
Explanation: 13 → 14 → 7 → 8 → 4 → 2 → 1.
Example 2
Input: s = "10"
Output: 1
Explanation: 2 → 1.
Example 3
Input: s = "1"
Output: 0
Constraints
1 <= s.length <= 500s consists of characters '0' and '1'.s[0] is '1'.
Hints for Number of Steps to Reduce a Number in Binary Representation to One
Hint 1
The number can be 500 bits long, so it will not fit in any built-in integer type.
Hint 2
Work on the bit string from the least significant end, carrying as in binary addition.
Hint 3
A 0 bit costs one step (a division); a 1 bit costs two (an addition then a division) and sets a carry.
How to solve Number of Steps to Reduce a Number in Binary Representation to One
Process the bits right to left with a carry. Each bit's cost is determined locally: dividing shifts the string right by one, and adding 1 to an odd number propagates a carry leftward.
Approach
- Start with
steps = 0andcarry = 0, and walkifrom the last index down to index 1. - Let
bit = s[i] + carry. Ifbit == 1the number is odd: add 1 (one step) then divide (another step), so add 2 tostepsand setcarry = 1. - Otherwise the number is even: add 1 step for the division, and set
carry = 1only ifbit == 2(a 1 plus an incoming carry). - After the loop, add
carry— a final carry means the leading 1 became10, which needs one more division.
Why it works
Dividing by two is exactly dropping the last bit, so sweeping right to left visits the bits in the order the algorithm consumes them. The carry encodes the pending +1 from the most recent odd step, which is precisely how binary addition propagates.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Parsing the string into an integer overflows for anything past 64 bits.
- Forgetting the trailing
+ carryundercounts whenever the final carry reaches the leading bit. - The loop must stop at index 1, not 0 — the leading bit is handled by the carry term.
Reference solution
Python
def numSteps(s: str) -> int:
steps = 0
carry = 0
for i in range(len(s) - 1, 0, -1):
bit = int(s[i]) + carry
if bit == 1:
steps += 2
carry = 1
else:
steps += 1
carry = 1 if bit == 2 else 0
return steps + carryJava
public static int numSteps(String s) {
int steps = 0, carry = 0;
for (int i = s.length() - 1; i >= 1; i--) {
int bit = (s.charAt(i) - '0') + carry;
if (bit == 1) {
steps += 2;
carry = 1;
} else {
steps += 1;
carry = bit == 2 ? 1 : 0;
}
}
return steps + carry;
}C++
int numSteps(string s) {
int steps = 0, carry = 0;
for (int i = (int) s.size() - 1; i >= 1; i--) {
int bit = (s[i] - '0') + carry;
if (bit == 1) {
steps += 2;
carry = 1;
} else {
steps += 1;
carry = bit == 2 ? 1 : 0;
}
}
return steps + carry;
}JavaScript
var numSteps = function(s) {
let steps = 0, carry = 0;
for (let i = s.length - 1; i >= 1; i--) {
const bit = Number(s.charAt(i)) + carry;
if (bit === 1) {
steps += 2;
carry = 1;
} else {
steps += 1;
carry = bit === 2 ? 1 : 0;
}
}
return steps + carry;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Bit Manipulation