Leetcode 67: Add Binary

1. Problem Statement (Simple Explanation)

You’re given two binary strings a and b (only '0' and '1').

You must:

• Compute a + b (as binary addition).

• Return the result as a binary string (no leading zeros except "0" itself).

2. Examples

Example 1:

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

• 11₂ = 3₁₀

• 1₂ = 1₁₀

• Sum = 4₁₀ = 100₂

Output: "100"

Example 2:

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

• 1010₂ = 10₁₀

• 1011₂ = 11₁₀

• Sum = 21₁₀ = 10101₂

Output: "10101"

3. Approach – Binary Addition with Carry (O(max(m,n)))

We simulate manual binary addition:

1. Use two pointers:

• i = len(a) - 1

• j = len(b) - 1

2. Use carry = 0.

3. While i >= 0 or j >= 0 or carry > 0:

• sum = carry

• If i >= 0: add a[i] - '0' to sum, decrement i.

• If j >= 0: add b[j] - '0' to sum, decrement j.

• New bit: sum % 2 (0 or 1).

• New carry: sum // 2 (0 or 1).

• Append the new bit to the result (note: we’re building it reversed).

4. Reverse the result string at the end.

Pseudo-code:

Complexity:

Let m = len(a), n = len(b):

• Time: O (max(m,n)) – single pass from right to left.

• Space: O (max(m,n)) for the result.

4. Java code

5. C code

6. C++ code

7. Python code

8. JavaScript code