rezzcode ∞

Posted on Feb 16

Leetcode Sunday #3

#algorithms #devjournal #leetcode

LeetCode 67: Add Binary

Difficulty: Easy

Time Spent: ~1 hour

This Sunday’s LeetCode challenge was about adding two binary strings, for example:

a = "1000"
b = "1011"

At first glance, this looked straightforward.

The Confident First Attempt

I immediately reached for what felt natural:

import strconv
Convert both binary strings to integers
Perform normal integer addition
Convert the result back to binary
Return the final string using strconv.Itoa

In Go, that meant importing strconv, parsing the strings, doing integer arithmetic, and then converting everything back.

Parse binary → integer
Add integers
Convert sum → binary string

Clean. Simple. Done.

However, this approach fails for very large inputs.

The problem constraints allow strings of significant length. If you assume something like:

len(a) = 1e9 + 1

the value will overflow a 64-bit integer. In fact, during submission, I encountered cases where the result turned negative due to overflow.

That immediately made it clear, and I knew I had to rethink of my approach:

The problem was not about numeric conversion.

It’s about simulating binary addition manually.

And was testing whether I understood binary addition itself.

Rethinking the Problem

Binary arithmetic only uses two digits: 0 and 1.

Binary addition follows the exact same logic as base-10 addition — only the threshold changes.

Base 10 Example

9 + 9 = 18

Write 8
Carry 1

Binary Equivalent

1 + 1 = 10

Write 0
Carry 1

So the process is identical:

Add digits from right to left
Keep track of a carry
Append the current digit
Move to the next position

and instead of converting entire strings into integers, I needed to simulate the manual addition process — digit by digit, from right to left.

Designing the Logic

To simulate this properly, I needed:

A variable to store the carry (upV)
A result string (str)
Two pointers starting from the end of each string

We always process from right to left, because addition starts from the least significant digit.

At each step:

Add the current digits
Add the carry
Store sum % 2
Update carry as sum / 2

For example illustration:

If we have...

a = "111"
b = "101"

We start with:

a[len(a)-1]
b[len(b)-1]

If both digits are 1, then:

1 + 1 = 0 (write)
carry = 1

One important implementation detail:

If we use:

str += "0"

we would build the string in reverse order.

So instead, we prepend:

str = "0" + str

About String Concatenation

You might ask:

Why not use strings.Builder for better performance?

The issue is that strings.Builder efficiently appends to the end — not the beginning.

Since we are prepending digits, what i needed was:

str = newDigit + str

so strings.Builder is efficient for appending — but not for prepending.

And since we’re building the number from right to left, prepending felt like the most straightforward option at the time.

If you know a cleaner or more performant approach for efficiently building the string in reverse order, feel free to share in the comments.

Final Working Solution

Here is the simplified implementation:

import "strconv"

func addBinary(a string, b string) string {
    x, y := len(a)-1, len(b)-1
    upV := 0
    str := ""

    for x >= 0 || y >= 0 {
        sum := upV

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

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

        str = strconv.Itoa(sum%2) + str
        upV = sum / 2
    }

    if upV > 0 {
        str = strconv.Itoa(upV) + str
    }

    return str
}

Why This Worked

We iterate once.
We simulate real binary addition.
We never convert the full string into an integer.
Time complexity is O(n).
Space complexity is O(n).

Key Takeaway

Sometimes, the problem labeled easy is not usually hard.

The logic is simple, but only if you think about it the right way.

This question isn’t about conversion — it’s about understanding how addition fundamentally works.

DEV Community