#67

Easy

LeetCode Problem Workspace

Add Binary

Add Binary involves summing two binary strings and returning the result as a binary string using math and string manipulation.

math string bit manipulation simulation

Problem Statement

You are given two binary strings a and b. Your task is to add them together and return the sum as a binary string. The binary strings may vary in length, but both consist only of '0' and '1' characters. The result should not contain leading zeros, except when the sum is zero.

To solve this problem, you can simulate the binary addition process, similar to how you would manually add binary digits. Start from the least significant bit and move towards the most significant, managing carryover as needed. The constraints indicate that the input strings can be large, so consider an efficient solution in both time and space.

Examples

Example 1

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

Output: "100"

Example details omitted.

Example 2

Input: a = "1010", b = "1011"

Output: "10101"

Example details omitted.

Constraints

1 <= a.length, b.length <= 104
a and b consist only of '0' or '1' characters.
Each string does not contain leading zeros except for the zero itself.

Solution Approach

Simulate Binary Addition

The most direct way to solve this problem is by simulating binary addition from the least significant bit (rightmost). Traverse both strings from right to left, adding corresponding digits along with any carry from the previous step. If the sum of the digits and carry exceeds 1, update the carry for the next step and append the binary result. Continue until both strings are fully processed.

Optimize with String Operations

To handle the binary addition more efficiently, it is important to minimize string manipulations. Using a list to store intermediate results or directly building the result string as you go can reduce overhead. This approach also allows for more optimized memory usage, especially when dealing with long strings.

Leverage Bit Manipulation

While not strictly necessary, bitwise operations could be used to optimize the solution further. Using bitwise XOR and AND operators for addition and carry calculations can speed up the process in some cases, especially when handling very large binary strings. This approach, however, requires careful attention to carry propagation and string building.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution depends on the length of the longer binary string, resulting in O(max(m, n)), where m and n are the lengths of the input strings a and b. The space complexity is O(max(m, n)) due to the space required for storing the result, which may be up to the length of the longest string plus one for the carry.

What Interviewers Usually Probe

Do you handle carry properly when adding binary digits?
Can you optimize the solution for large input sizes?
Will you account for cases where the binary strings have different lengths?

Common Pitfalls or Variants

Common pitfalls

Ignoring the carry during addition can lead to incorrect results.
Not managing string length differences properly may cause out-of-bounds errors.
Forgetting to remove leading zeros from the final result can lead to invalid outputs.

Follow-up variants

Add Two Binary Strings with Overflow Handling
Multiply Binary Numbers
Convert Binary Sum to Decimal and Then Binary

FAQ

How do you add two binary numbers without using built-in functions?

To add binary numbers manually, simulate the binary addition process starting from the rightmost bit, managing the carry as you go.

Can bitwise operations speed up the Add Binary solution?

Yes, bitwise operations like XOR and AND can be used to handle binary addition and carry calculations more efficiently, especially for large strings.

How should you handle carry in binary addition?

During binary addition, if the sum exceeds 1, a carry of 1 is passed to the next higher bit. Ensure this is managed for each pair of bits.

What are the time and space complexities for the Add Binary problem?

The time complexity is O(max(m, n)) where m and n are the lengths of the input strings. Space complexity is also O(max(m, n)) for storing the result.

What if the binary strings have different lengths?

If the binary strings have different lengths, align them by padding the shorter one with leading zeros, then proceed with the addition as usual.

terminal

Solution

Solution 1: Simulation

We use a variable $\textit{carry}$ to record the current carry, and two pointers $i$ and $j$ to point to the end of $a$ and $b$ respectively, and add them bit by bit from the end to the beginning.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        ans = []
        i, j, carry = len(a) - 1, len(b) - 1, 0
        while i >= 0 or j >= 0 or carry:
            carry += (0 if i < 0 else int(a[i])) + (0 if j < 0 else int(b[j]))
            carry, v = divmod(carry, 2)
            ans.append(str(v))
            i, j = i - 1, j - 1
        return "".join(ans[::-1])

Continue Practicing

#13 roman to integer #12 integer to roman #166 fraction to recurring decimal