← Back to Index

📚 Number of Steps to Reduce a Binary Number to One – Java Cheat Sheet

📌 What Is It?

The Number of Steps to Reduce a Binary Number to One problem involves reducing a binary number (given as a string) to 1 by performing the following operations:

• If the number is even, divide it by 2.
• If the number is odd, add 1 to it.

The goal is to determine the minimum number of steps required to reduce the binary number to 1.

🧱 Pattern Template

Simulating Binary Operations

class Solution {
    public int numSteps(String s) {
        int steps = 0;
        int carry = 0;

        // Start from the least significant bit and process toward the most significant bit
        for (int i = s.length() - 1; i > 0; i--) {
            if (s.charAt(i) - '0' + carry == 1) {
                // If the bit is 1 (odd), add 1 (carry) and increment steps
                carry = 1;
                steps += 2; // Add 1 and divide by 2
            } else {
                // If the bit is 0 (even), just divide by 2
                steps += 1;
            }
        }

        // Handle the most significant bit
        return steps + carry;
    }
}

▶️ View Animation

📊 Time Complexity

• Time Complexity: O(N), where N is the length of the binary string.
• Space Complexity: O(1), as we use only a constant amount of extra space.

✅ Use Cases

• Simulating binary operations efficiently.
• Understanding bit manipulation and binary arithmetic.

📘 Common LeetCode Problems

• 1404. Number of Steps to Reduce a Number in Binary Representation to One [Medium] Binary

🧪 Example

Input: s = "1101"
Output: 6

Explanation:
- "1101" is odd, add 1 → "1110"
- "1110" is even, divide by 2 → "111"
- "111" is odd, add 1 → "1000"
- "1000" is even, divide by 2 → "100"
- "100" is even, divide by 2 → "10"
- "10" is even, divide by 2 → "1"

💡 Pro Tips

• Simulate the operations directly on the binary string without converting it to an integer.
• Use a carry variable to handle the addition of 1 when the number is odd.
• Focus on the most significant bit to determine when the process ends.

🎥 Video Explanation

For a detailed explanation, watch this video: Rearranging Fruits Problem Explanation by NeetCode IO