How do you solve Add Binary on LeetCode?

Add Binary (LeetCode #67) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Binary addition is similar to decimal addition but only involves two digits (0 and 1).

What is the brute force solution for Add Binary?

The brute force approach for Add Binary is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves converting the binary strings to decimal integers, adding them, and then converting the result back to a binary string. This is straightforward but not efficient for large strings. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Add Binary?

Add Binary uses the following concepts: Math, String, Bit Manipulation, Simulation. The recommended patterns to study are: Bit Manipulation, Simulation.

What are the interview tips for Add Binary?

Always clarify if you can use built-in functions for conversions. Discuss edge cases, such as when one string is longer than the other. Practice writing out the binary addition process on paper to visualize carries.

What are common mistakes when solving Add Binary?

Forgetting to handle the final carry after the loop. Not reversing the result string before returning it.

#67

Add Binary

Easy

MathStringBit ManipulationSimulationBit ManipulationSimulation

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution simulates binary addition directly, handling carries as we iterate through both strings from the end. This avoids conversions and works directly with the binary representation.

⚙️

Algorithm

6 steps

1Step 1: Initialize an empty result string and a carry variable set to 0.
2Step 2: Iterate from the end of both strings towards the start until both strings are processed.
3Step 3: For each bit, calculate the sum of the bits and the carry.
4Step 4: Determine the new bit to append to the result and update the carry.
5Step 5: If there's a carry left after the loop, append it to the result.
6Step 6: Reverse the result string before returning.

solution.py15 lines

1def addBinary(a: str, b: str) -> str:
2    result = []
3    carry = 0
4    i, j = len(a) - 1, len(b) - 1
5    while i >= 0 or j >= 0 or carry:
6        total = carry
7        if i >= 0:
8            total += int(a[i])
9            i -= 1
10        if j >= 0:
11            total += int(b[j])
12            j -= 1
13        result.append(str(total % 2))
14        carry = total // 2
15    return ''.join(result[::-1])

ℹ

Complexity note: The time complexity is O(n) because we process each bit of both strings once. The space complexity is O(n) due to the result string that we build.

1Binary addition is similar to decimal addition but only involves two digits (0 and 1).
2Handling carry is crucial in binary addition, just like in decimal.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.