The O(n) Club: Add Binary Strings: The O(n) Club’s Guide To DIY Bit Addition (No parseInt Cheating)

The O(n) Club: Add Binary Strings—Manual Labor For Digital Geniuses

⚡ TL;DR

Add two binary strings and return the sum as (surprise!) a binary string. Don’t just mash them into parseInt—that’s the equivalent of ordering takeout when the interviewer wants you to cook. Here’s the lazy version (not for real interviews!):

// Quick but risky:
return Integer.toBinaryString(
  Integer.parseInt(a, 2) + Integer.parseInt(b, 2)
);

🧠 How Devs Usually Mess This Up

Most Java devs spot the problem and immediately try a shortcut: parse those strings, add, convert back. Great—unless someone brings a 100,000-digit binary and the JVM taps out. Or the interviewer gets that look that means, “You didn’t actually think I’d make this that easy, did you?” Also, if you try adding ‘1’ + ‘1’, well, Java thinks you mean 98 (don’t ask, blame ASCII).
Oh, and skipping the carry? That’s the binary way to fail every math test and your technical round.

🔍 What’s Actually Going On

Think like you’re seven, adding numbers on scratch paper, but now you only own two digits: 0 and 1. Start at the right end, add each pair, keep track of the “overflowing” ones (the carry!), and if you run out of digits on either number or hit the end with a leftover carry, don’t just walk off the stage—add it in. You’re simulating digital logic, just with more caffeine and less silicon.

• Align both numbers right-side (least significant bit first).
• Add each pair, plus carry, from right to left.
• Write down (sum mod 2) and update carry (sum / 2).
• Keep going until you finish both numbers and the carry is zero.
• Reverse the result, since you built it backwards. Drama!

🛠️ PseudoCode

• Set i, j = rightmost indices of a and b. carry = 0.
• Loop: While i >= 0 or j >= 0 or carry != 0:
• Let sum = carry.
• If i >= 0: sum += a.charAt(i–) – ‘0’.
• If j >= 0: sum += b.charAt(j–) – ‘0’.
• Append (sum % 2) to your result string.
• Set carry = sum / 2.
• After loop: reverse the result string.

Bam. Same moves as grade-school math, fewer fingers involved.

💻 The Code

public String addBinary(String a, String b) {
    StringBuilder res = new StringBuilder();
    int i = a.length() - 1, j = b.length() - 1, carry = 0;
    while (i >= 0 || j >= 0 || carry != 0) {
        int sum = carry;
        if (i >= 0) sum += a.charAt(i--) - '0';
        if (j >= 0) sum += b.charAt(j--) - '0';
        res.append(sum % 2);
        carry = sum / 2;
    }
    return res.reverse().toString();
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Don’t miss the extra carry at the very end—otherwise, enjoy debugging your “almost right” sum.
• Never assume strings are the same length. This isn’t kindergarten—life isn’t fair and neither are your inputs.
• If you see Integer.parseInt, hope the inputs are small. Overflow is lurking like a cat under the desk, ready to pounce.
• Time: O(n) (where n = max length). Space: O(n) for new string. If you’re sweating about memory here, you probably have bigger issues.

🧠 Interviewer Brain-Tattoo

When in doubt: add like you’re seven, code like you’re on caffeine, and never let parseInt do your homework for you.