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

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

Understanding the Visualization

Input

Binary string representation

Process

Apply reduction rules until reaching '1'

Output

Total number of steps taken

Key Takeaway

🎯 Key Insight: Count steps efficiently by analyzing binary patterns - each '1' (except first) adds an extra step beyond base divisions

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

Approach	Time	Space	Notes
✓ Convert to Integer	O(n)	O(1)	Convert binary string to integer, apply rules until reaching 1
Optimized Counting	O(n)	O(1)	Count steps by analyzing binary pattern without full simulation
Binary String Simulation	O(n)	O(n)	Simulate operations directly on binary string without conversion

Convert to Integer — Algorithm Steps

Convert binary string to integer
While number > 1: if even divide by 2, if odd add 1
Count each operation

Visualization

Tap to expand

Step-by-Step Walkthrough

Convert

Binary to integer conversion

Apply Rules

Even: divide by 2, Odd: add 1

Count Steps

Track operations until reaching 1

Code -

solution.c — C

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

int solution(char* s) {
    long long num = 0;
    int len = strlen(s);
    
    for (int i = 0; i < len; i++) {
        num = num * 2 + (s[i] - '0');
    }
    
    int steps = 0;
    while (num > 1) {
        if (num % 2 == 0) {
            num /= 2;
        } else {
            num += 1;
        }
        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)

At most 2n operations where n is the number of bits

✓ Linear Growth

Space Complexity

O(1)

Only storing integer value and counter

✓ 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Convert to Integer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler