Add Binary Leetcode Problem 67 [Python Solution]

In this blog post, we will discuss the LeetCode problem Add Binary. This is an easy-level problem that falls under the category of Bit Manipulation.

The goal is to add two binary strings, a and b, and return their sum as a binary string.

Problem Overview

Given two binary strings, a and b, our task is to compute their sum as binary strings.

Binary addition follows the same rules as decimal addition, but with a base of 2. Here’s how binary addition works:

0 + 0 results in 0
0 + 1 results in 1
1 + 0 results in 1
1 + 1 results in 0 with a carry of 1

To add two binary strings, we start from the least significant bit (rightmost) and move towards the most significant bit (leftmost).

If the sum of two bits at the same position is greater than 1, we need to carry over to the next position.

Example 1:

Let’s work through an example:

Input: a = "11", b = "1"
Output: "100"

Here’s the step-by-step process of adding these two binary strings:

Adding the rightmost bits: 1 + 1 results in 0, with a carry of 1.
Moving to the next bit: 1 + 0 results in 1.
Finally, there’s a carry from the previous step, so we add it to the leftmost bit, resulting in 1.

The final sum is "100", which matches the output.

Understanding Constraints

The problem comes with certain constraints:

1 <= a.length, b.length <= 104: This means that the input binary strings a and b can be quite long, with a maximum length of 10,000.
a and b consist only of ‘0’ or ‘1’ characters.
Each string does not contain leading zeros except for the zero itself.

This constraint ensures that the input strings do not have unnecessary leading zeros, making the problem more straightforward.

Now, let’s dive into the solution.

Add Binary LeetCode Problem Solution

We will provide both the Python code solution and the explanation for the solution.

Python Code Solution

View on GitHub ➹

def addBinary(self, a: str, b: str) -> str:
    res = ""
    carry = 0

    a, b = a[::-1], b[::-1]
    for i in range(max(len(a), len(b)):
        bit_a = ord(a[i]) - ord('0') if i &lt; len(a) else 0
        bit_b = ord(b[i]) - ord('0') if i &lt; len(b) else 0

        total = bit_a + bit_b + carry
        char = str(total % 2)
        res = char + res
        carry = total // 2

    if carry:
        res = "1" + res

    return res

Now, let’s break down the solution step by step.

Initialize an empty string res to store the result and a carry variable, initially set to 0.
Reverse both input strings, a and b. Reversing the strings allows us to perform the addition from right to left, just as we do with manual binary addition.
Use a for loop to iterate through the longer of the two input strings. This ensures that we consider all digits in both strings.
Inside the loop, calculate bit_a and bit_b:
- bit_a is the integer value of the current character in the reversed a.
We subtract the ASCII value of ‘0’ to get the actual integer value.
- bit_b is computed similarly for the current character in the reversed b.
If we have reached the end of one of the strings, we assign a value of 0 to the corresponding bit.
Calculate the total by adding bit_a, bit_b, and the carry from the previous iteration.
Compute the current binary digit (0 or 1) based on the total % 2 and convert it to a string.
Append the computed binary digit to the res string.
Since we are traversing from right to left, we add the new digit to the beginning of the result string to maintain the correct order.
Update the carry for the next iteration. We calculate it as total // 2.
After the loop completes, there might still be a carry left. If carry is not equal to zero, add a ‘1’ to the beginning of the res string.
Finally, return the res string as the binary sum of the input strings a and b.

This solution handles binary addition efficiently and is based on a clear and intuitive approach.

It reverses the input strings to simplify digit-wise addition and properly handles carries.

Additionally, it follows the constraints provided by the problem.

Time and Space Complexity

Time Complexity: The time complexity of this solution is O(max(N, M)), where N is the length of string a, and M is the length of string b.

We iterate through the longer string once, and the addition and other operations are performed in constant time for each iteration.

Space Complexity: The space complexity is O(max(N, M)) as well.

The res string stores the binary result, which can be as long as the longer input string.

Reasoning Behind Our Approach

The reasoning behind this approach is to simulate manual binary addition, considering the carry as we go.

Reversing the input strings allows us to perform digit-wise addition efficiently, and by correctly handling the carry, we obtain the desired result.

In conclusion, the Add Binary problem on LeetCode is a simple yet interesting problem that requires you to perform binary addition efficiently.

We’ve provided a Python solution that follows a clear and intuitive approach.

This solution handles the constraints of the problem and ensures that the output string does not contain unnecessary leading zeros.

If you have any questions or suggestions, please feel free to comment and share your thoughts.

You can also visit the problem on LeetCode for further practice.

Happy coding!

Add Binary Leetcode Problem 67 [Python Solution]

Example 1:

Add Binary LeetCode Problem Solution

Python Code Solution

Time and Space Complexity

Related Interview Questions By Company:

Related Interview Questions By Difficulty:

Related Interview Questions By Category:

Reasoning Behind Our Approach

Written By

CID

Tags