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

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: divide it by 2.

If the current number is odd: add 1 to it.

It is guaranteed that you can always reach one for all test cases.

Input & Output

Example 1 — Basic Case

$ Input: s = "1101"

› Output: 6

💡 Note: "1101" (13) → "1110" (14) → "111" (7) → "1000" (8) → "100" (4) → "10" (2) → "1" (1). Total: 6 steps.

Example 2 — Even Number

$ Input: s = "10"

› Output: 1

💡 Note: "10" (2) → "1" (1). Only one division by 2 needed.

Example 3 — Already One

$ Input: s = "1"

› Output: 0

💡 Note: Already at 1, no steps needed.

Constraints

1 ≤ s.length ≤ 500
s consists only of '0' or '1'
s[0] == '1'

Visualization

Tap to expand

Asked in

f Meta 15 a Amazon 12

The key insight is recognizing that we can count steps without full simulation. For a binary string, each '1' bit (except the first) requires an additional step beyond the base divisions. The optimized approach counts steps in O(n) time with O(1) space by analyzing bit patterns.

Common Approaches

✓ Binary String Simulation

⏱️ Time: O(n) Space: O(n)

Process the binary string character by character to simulate the operations. When the number is odd (ends with '1'), we add 1, which in binary flips consecutive trailing 1s to 0s and adds a carry. When even (ends with '0'), we divide by 2 by removing the last bit.

Convert to Integer

⏱️ Time: O(n) Space: O(1)

First convert the binary string to an integer, then repeatedly apply the rules (divide by 2 if even, add 1 if odd) while counting steps. This approach is straightforward but may overflow for very large numbers.

Optimized Counting

⏱️ Time: O(n) Space: O(1)

Instead of simulating each step, we can count steps more efficiently. For each '1' bit (except the leftmost), we need one step to make it '0' by adding 1, plus one step to divide by 2. For each '0' bit, we just need one step to divide by 2. This gives us a formula to count total steps.

Binary String Simulation — Algorithm Steps

Check if binary ends with '0' (even) or '1' (odd)
If odd, simulate adding 1 by handling carries
If even, remove last bit (divide by 2)
Continue until string becomes '1'

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Last Bit

0 means even, 1 means odd

Apply Operation

Even: remove last bit, Odd: add 1

Repeat

Continue until string becomes '1'

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void addOne(char* s) {
    int len = strlen(s);
    int carry = 1;
    
    for (int i = len - 1; i >= 0 && carry; i--) {
        if (s[i] == '0') {
            s[i] = '1';
            carry = 0;
        } else {
            s[i] = '0';
        }
    }
    
    if (carry) {
        memmove(s + 1, s, len + 1);
        s[0] = '1';
    }
}

int solution(char* s) {
    int steps = 0;
    int len = strlen(s);
    
    while (strcmp(s, "1") != 0) {
        len = strlen(s);
        if (s[len - 1] == '0') {  // Even
            s[len - 1] = '\0';  // Divide by 2
        } else {  // Odd
            addOne(s);
        }
        steps++;
    }
    
    return steps;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each operation processes the string once, at most 2n operations

✓ Linear Growth

Space Complexity

O(n)

String operations may create new strings of length n

✓ Linear Space

32.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary String Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler