NUHMAN.com

Introduction

LeetCode 67: Add Binary is a classic algorithm problem where you're given two binary strings and need to return their sum—also as a binary string. It's a great exercise for simulating binary arithmetic, handling carry logic, and working with strings in reverse.

In this article, we’ll walk through how to implement this in Go, a language that makes string manipulation straightforward but requires you to be careful with immutability and rune vs byte handling.

Problem Statement

Given two binary strings a and b, return their sum as a binary string.

Examples:

go

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

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

Constraints

• 1 <= len(a), len(b) <= 10⁴
• a and b consist only of '0' or '1' characters.
• Strings do not contain leading zeros except for "0" itself.

Approach: Two-Pointer + Carry

The idea is to simulate binary addition manually, starting from the end (least significant bits):

1. Initialize two pointers i and j for a and b, starting from the rightmost characters.
2. Maintain a carry initialized to 0.
3. Iterate as long as i or j is in bounds or there's a carry.
4. At each step:

• Convert a[i] and b[j] to integer if in bounds.
• Compute the sum of digits and carry.
• Append the result of sum % 2 to the result string.
• Update carry = sum / 2.

1. Reverse and return the final result.

Go Implementation

go

func addBinary(a string, b string) string {
    i, j := len(a)-1, len(b)-1
    carry := 0
    result := make([]byte, 0)

    for i >= 0 || j >= 0 || carry > 0 {
        sum := carry

        if i >= 0 {
            sum += int(a[i] - '0')
            i--
        }

        if j >= 0 {
            sum += int(b[j] - '0')
            j--
        }

        result = append(result, byte(sum%2)+'0')
        carry = sum / 2
    }

    // Reverse the result since we added digits from least significant to most
    for left, right := 0, len(result)-1; left < right; left, right = left+1, right-1 {
        result[left], result[right] = result[right], result[left]
    }

    return string(result)
}

Explanation

• We loop through the strings from the end to the beginning.
• We handle binary addition manually using ASCII subtraction ('1' - '0' = 1).
• If one string is longer than the other, we keep adding from it as long as it has characters left.
• We use a []byte slice to efficiently build the result.
• Finally, we reverse the result because we added digits in reverse order.

Time and Space Complexity

MetricComplexityTime ComplexityO(max(n, m))Space ComplexityO(max(n, m))

Where n and m are the lengths of a and b. We process each digit once, and the result will have at most max(n, m) + 1 digits.

Edge Cases Covered

• "0" + "0" → "0"
• "1" + "1" → "10"
• "1111" + "1" → "10000"
• Uneven string lengths → correctly handled

Conclusion

LeetCode 67 teaches you how to manually simulate arithmetic operations. This is a foundational technique useful in problems involving large numbers or custom numeric formats. In Go, manipulating strings like this gives you a solid grip on bytes, slices, and efficient memory usage.