Scale Engineer

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

Med
#1300Time: O(N^2), where N is the length of the string `s`. The number of bits in the `BigInteger` is N. The number of steps in the reduction process is on the order of O(N). Each addition or division operation on an N-bit `BigInteger` takes O(N) time. Therefore, the total time complexity is O(N * N) = O(N^2).Space: O(N), where N is the length of the string `s`. This is required to store the `BigInteger` object, which needs space proportional to the number of bits.2 companies
Patterns
Bit Manipulation
Data structures
String
Companies
GrabGeico

Prompt

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'

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into code. Since the number represented by the binary string s can be very large (up to 2^500 - 1), we cannot use standard primitive data types like long. Java's java.math.BigInteger class is perfect for handling arithmetic on such large numbers.

Algorithm

  • Convert the input binary string s into a java.math.BigInteger object.
  • Initialize a steps counter to 0.
  • Create BigInteger constants for ONE and TWO for convenience.
  • Enter a loop that continues as long as the BigInteger value is not equal to ONE.
  • Inside the loop, check if the number is even or odd. A BigInteger is even if its least significant bit is 0. This can be checked using the testBit(0) method. If testBit(0) returns false, the number is even.
  • If the number is even, divide it by TWO.
  • If the number is odd, add ONE to it.
  • Increment the steps counter in each iteration.
  • Once the loop terminates (when the number becomes ONE), return the total steps.

Walkthrough

The algorithm starts by converting the input binary string s into a BigInteger object. It then enters a loop that continues as long as the number is not equal to one. Inside the loop, it checks if the number is even or odd. If the number is even, it's divided by two. If it's odd, one is added to it. A counter is incremented for each step (either division or addition). The loop terminates when the number becomes one, and the total count of steps is returned.

import java.math.BigInteger; class Solution {    public int numSteps(String s) {        BigInteger num = new BigInteger(s, 2);        final BigInteger ONE = BigInteger.ONE;        final BigInteger TWO = new BigInteger("2");        int steps = 0;         while (!num.equals(ONE)) {            // testBit(0) checks the least significant bit.            // If it's 0, the number is even.            if (!num.testBit(0)) {                 num = num.divide(TWO);            } else {                num = num.add(ONE);            }            steps++;        }        return steps;    }}

Complexity

Time

O(N^2), where N is the length of the string `s`. The number of bits in the `BigInteger` is N. The number of steps in the reduction process is on the order of O(N). Each addition or division operation on an N-bit `BigInteger` takes O(N) time. Therefore, the total time complexity is O(N * N) = O(N^2).

Space

O(N), where N is the length of the string `s`. This is required to store the `BigInteger` object, which needs space proportional to the number of bits.

Trade-offs

Pros

  • Simple to understand and implement as it directly follows the problem description.

  • Robustly handles arbitrarily large numbers without risk of overflow.

Cons

  • Less efficient compared to other approaches due to the overhead of BigInteger operations.

  • Higher memory usage as it needs to store the large number in a BigInteger object.

Solutions

class Solution {public  int numSteps(String s) {    boolean carry = false;    int ans = 0;    for (int i = s.length() - 1; i > 0; --i) {      char c = s.charAt(i);      if (carry) {        if (c == '0') {          c = '1';          carry = false;        } else {          c = '0';        }      }      if (c == '1') {        ++ans;        carry = true;      }      ++ans;    }    if (carry) {      ++ans;    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem