LeetCode 1404: Number of Steps to Reduce a Number in Binary Representation to One Solution

Master LeetCode problem 1404 (Number of Steps to Reduce a Number in Binary Representation to One), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

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

Medium

String Bit Manipulation

Problem Explanation

Explanation:

To solve this problem, we can iterate through the binary string from right to left. If the current bit is '0', we perform a division operation by 2. If the current bit is '1', we increment the number by 1 and then perform a division operation by 2. We keep track of the number of steps taken until the number becomes 1.

Time Complexity: O(n) where n is the length of the binary string s. Space Complexity: O(1)

Solution Code

class Solution {
    public int numSteps(String s) {
        int steps = 0;
        int carry = 0;
        
        for (int i = s.length() - 1; i > 0; i--) {
            steps++;
            if (s.charAt(i) - '0' + carry == 1) {
                carry = 1;
                steps++;
            }
        }
        
        return steps + carry;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1404 (Number of Steps to Reduce a Number in Binary Representation to One)?

This page provides optimized solutions for LeetCode problem 1404 (Number of Steps to Reduce a Number in Binary Representation to One) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1404 (Number of Steps to Reduce a Number in Binary Representation to One)?

The time complexity for LeetCode 1404 (Number of Steps to Reduce a Number in Binary Representation to One) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1404 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1404 in Java, C++, or Python.

Back to LeetCode Solutions