DEV Community

Cover image for ⚙️ Beginner-Friendly Guide - Leetcode Problem 1404 (C++, Python, JavaScript)
Om Shree
Om Shree

Posted on

⚙️ Beginner-Friendly Guide - Leetcode Problem 1404 (C++, Python, JavaScript)

#programming #cpp #python #javascript

Converting binary strings into integers can be tricky when the numbers are massive. This problem challenges you to manipulate a binary representation directly, simulating mathematical operations without actually converting the string into a standard number type that might overflow.

Problem Summary

You're given:

  • A string s representing a positive integer in binary format.

Your goal:

  • Return the total number of steps to reduce this number to 1.
  • If the number is even, divide it by 2.
  • If the number is odd, add 1.

Intuition

The most efficient way to solve this is to look at how binary numbers behave during these operations. Dividing an even binary number by 2 is the same as removing the last digit if that digit is '0'. Adding 1 to an odd binary number (where the last digit is '1') triggers a "carry" that ripples through the string.

Instead of simulating the carry every single time, we can use a clever observation:

  1. Trailing Zeros: Any '0' at the end of the original string represents an even number. We simply "chop" it off and count 1 step.
  2. The First Odd Encounter: Once we hit a '1' that isn't the very first bit, the number becomes odd. Adding 1 to this will turn that '1' into a '0' and carry a '1' to the left.
  3. The Ripple Effect: After the first addition of 1, every '1' we encounter will eventually become a '0' and require 1 step to divide, while every '0' will turn into a '1' due to the carry, requiring 2 steps (one to add 1, one to divide).

Walkthrough: Understanding the Examples

Example 1: s = "1101"

  • Step 1: The last digit is '1' (Odd). Add 1 to get "1110". (1 step)
  • Step 2: The last digit is '0' (Even). Divide by 2 to get "111". (1 step)
  • Step 3: The last digit is '1' (Odd). Add 1 to get "1000". (1 step)
  • Step 4: Last digit '0'. Divide by 2 to get "100". (1 step)
  • Step 5: Last digit '0'. Divide by 2 to get "10". (1 step)
  • Step 6: Last digit '0'. Divide by 2 to get "1". (1 step)
  • Total: 6 steps.

C++ Solution 

class Solution {
 public:
  int numSteps(string s) {
    int ans = 0;
    // Remove trailing even zeros
    while (s.back() == '0') {
      s.pop_back();
      ++ans;
    }
    // If the remaining string is just "1", we are done
    if (s == "1")
      return ans;

    // If we reach here, the number was odd at some point.
    // We add 1 step for the initial addition that creates the carry.
    ++ans;
    for (int i = 1; i < s.length(); ++i) {
      // If bit is '1', it becomes '0' with carry: 1 step.
      // If bit is '0', it becomes '1' with carry, then '0': 2 steps.
      ans += (s[i] == '1' ? 1 : 2);
    }

    return ans;
  }
};
Enter fullscreen mode Exit fullscreen mode

Python Solution 

class Solution:
    def numSteps(self, s: str) -> int:
        ans = 0
        s_list = list(s)

        # Remove trailing zeros (dividing even numbers)
        while s_list and s_list[-1] == '0':
            s_list.pop()
            ans += 1

        # If the string is now just "1", return steps
        if "".join(s_list) == "1":
            return ans

        # Handle the carry logic for the remaining bits
        ans += 1
        for i in range(1, len(s_list)):
            if s_list[i] == '1':
                ans += 1
            else:
                ans += 2

        return ans
Enter fullscreen mode Exit fullscreen mode

JavaScript Solution 

/**
 * @param {string} s
 * @return {number}
 */
var numSteps = function(s) {
    let ans = 0;
    let chars = s.split('');

    // Remove trailing zeros
    while (chars.length > 0 && chars[chars.length - 1] === '0') {
        chars.pop();
        ans++;
    }

    // Check if we reached the value 1
    if (chars.join('') === "1") {
        return ans;
    }

    // Initial addition step
    ans++;
    for (let i = 1; i < chars.length; i++) {
        // Logic: '1' needs 1 step, '0' needs 2 steps due to carry
        ans += (chars[i] === '1' ? 1 : 2);
    }

    return ans;
};
Enter fullscreen mode Exit fullscreen mode

Key Takeaways

  • Binary Manipulation: Understanding that dividing by 2 in binary is a simple right-shift (removing the last bit).
  • Carry Logic: Recognizing how a single addition can change all subsequent bits in a sequence.
  • Efficiency: By processing the string from the end or using a single pass, we achieve a time complexity of $O(n)$, where $n$ is the length of the string.

Final Thoughts

This problem is a fantastic example of why we shouldn't always rely on built-in integer types. In a real-world scenario, such as cryptography or large-scale data processing, you often deal with numbers far larger than what a 64-bit integer can hold. Mastering string-based arithmetic is a vital skill for handling high-precision calculations or binary protocols.

Top comments (0)