Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Add two binary strings exactly like grade-school addition: walk both from the right, sum the two bits plus a carry, append (sum % 2) as the result digit, and carry (sum / 2) into the next column. Keep going while either string has digits left OR the carry is nonzero, then reverse. O(max(m, n)) time. Don't convert to int — the strings can be up to 10⁴ bits, which overflows fixed-width integers.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you simulate column addition cleanly with a carry instead of converting to a built-in integer type (which overflows on long inputs), and whether your loop condition correctly handles unequal lengths and a final carry.
Where candidates slip
Parsing the strings to int/long (overflows beyond ~64 bits), dropping the final carry so "1"+"1" returns "0", or building the result with immutable string concatenation (O(n²)).
How to stand out
Name the overflow trap immediately ('10⁴ bits won't fit in a long, so I simulate'), fold the carry into the loop condition, and note the skeleton generalises to Add Two Numbers and Add Strings.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewtotal = carryi >= 0?YesNoExplore the full treeCollapse the tree
How to read it:For each column: total = bitA + bitB + carryIn; output bit is total % 2; carryOut is total / 2.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Convert to Integer, Add, Reformat (Naive — Don't Ship)
1Hint 1Explore hintHide hint
The tempting one-liner: parse both strings as base-2 integers, add them, convert the sum back to a binary string.
2Hint 2Explore hintHide hint
Ask: how big can the inputs be? 10⁴ bits. Does that fit in the language's integer type?
3Hint 3Explore hintHide hint
In Java/C++ it overflows long well before 10⁴ bits; in Python big-ints work but the interviewer almost always wants the simulation. Treat this as the anti-pattern.
A · Core idea
The shortcut everyone thinks of first: Integer.parseInt(a, 2) + Integer.parseInt(b, 2), then Integer.toBinaryString(sum).
Why it's seductive. It's two library calls and reads like the problem statement. For tiny inputs it even returns the right answer.
Why it's wrong here. The constraints allow strings up to 10⁴ bits. A 32-bit int overflows past 31 bits and a 64-bit long past 63 — both vastly smaller than 10⁴. So for any realistically long input the parse either throws or silently wraps to garbage. The problem is designed to punish this shortcut; the binary-string format is a signal that the value may not fit a machine word.
The Python caveat. Python's integers are arbitrary precision, so int(a, 2) + int(b, 2) then bin(...)[2:] actually works for any length. But naming this as your answer in an interview usually earns a follow-up: 'now do it without bignum / in a language without it.' The point of the question is the carry simulation, so treat the conversion as a remark, not a solution.
Conclusion. Acknowledge the one-liner, state the overflow failure mode out loud, and pivot to the digit-by-digit simulation that works regardless of length or language.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
a = "11", b = "1"parse
int("11",2)=3, int("1",2)=1
fine for tiny inputs"100"C · Code with teaching comments
Reference implementation preview// NOT robust: overflows for inputs longer than ~63 bits. public String addBinary(String a, String b) { long x = Long.parseLong(a, 2); long y = Long.parseLong(b, 2); return Long.toBinaryString(x + y);Explore the full codeHide the full code
D · Why it works and complexityO(m + n) timeO(m + n) spaceOpen the invariant and proofExplore the proofHide the proof
The binary-string input format is a deliberate hint that the value may exceed native integer width. Recognising that converting-to-int is an overflow trap (in fixed-width languages) is itself part of what the interviewer is testing.
ComplexityO(m + n) time, O(m + n) space — Parsing and formatting are linear in the digit count, but the fixed-width integer path is simply incorrect for inputs beyond ~64 bits — correctness, not speed, is the problem.
E · Edge cases and pitfalls5a, b each 10⁴ bits (Java) — Long.parseLong throws NumberFormatException / overflows — approach fails.Explore edge casesHide edge cases
Edge cases handled
a, b each 10⁴ bits (Java)Long.parseLong throws NumberFormatException / overflows — approach fails.a = "0", b = "0"Returns "0" — fine, but doesn't justify the approach.
Pitfalls
- Assuming the input fits in int/long — it doesn't for long strings.
- Relying on Python big-ints in an interview that expects the manual carry.
- Treating a correct tiny-input result as proof of general correctness.
Approach 2 of 2 · Optimal
Right-to-Left Carry Simulation (Optimal)
1Hint 1Explore hintHide hint
Add the way you learned in school: align the numbers at the right, add column by column, carry the overflow left.
2Hint 2Explore hintHide hint
Two pointers i and j start at the last index of a and b. Each step compute total = carry + (a[i] if i>=0) + (b[j] if j>=0); the result bit is total % 2 and the new carry is total / 2.
3Hint 3Explore hintHide hint
Loop while i >= 0 OR j >= 0 OR carry != 0 so the final carry produces its own leading bit. Build the bits reversed, then reverse once.
A · Core idea
This is grade-school column addition, in base 2, executed right to left.
The per-column rule. Maintain two indices i, j at the ends of a and b, and a single carry. Each iteration computes total = carry + bitA + bitB, where bitA/bitB are 0 if that string is already exhausted (i < 0 / j < 0). Because each of the three addends is 0 or 1, total ranges over 0..3. The bit we emit for this column is total % 2, and what we push into the next column is carry = total / 2 — which is therefore always 0 or 1. That % 2 / / 2 pair is the entire arithmetic of binary addition.
Why the loop condition includes the carry. The most common bug is stopping as soon as both strings run out. Consider "1" + "1": after the only column, total = 2, we emit bit 0 and set carry = 1. If the loop ended now we'd return "0" — wrong; the answer is "10". By looping while i >= 0 OR j >= 0 OR carry != 0, that leftover carry runs one more iteration (with both bits treated as 0), emitting the top bit 1. This is exactly why the result can be one digit longer than the longer input.
Why right-to-left and why we reverse. Addition carries flow from least-significant to most-significant digit, which are the rightmost characters of each string. So we naturally produce the answer's bits from least- to most-significant — i.e. backwards. We append them to a buffer and reverse once at the very end (O(n)), rather than prepending each bit (which would be O(n²) with shifting).
Why a mutable buffer matters. Strings are immutable in Java and Python; concatenating a character per column rebuilds the whole string each time, turning the routine quadratic. Use a StringBuilder (Java) or a list you ''.join at the end (Python). Decode characters with c - '0' in Java and int(c) in Python. The whole thing is one linear pass, correct for arbitrary lengths, no integer type involved — which is precisely why it sidesteps the overflow trap.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
a = "11", b = "1"Interactive diagram
Carry propagating through "11" + "1"
i=1, j=0, carry=0Each column emits total%2 and forwards total/2; the trailing carry becomes the new leading bit.
"100"C · Code with teaching comments
D · Why it works and complexityO(max(m, n)) timeO(max(m, n)) spaceOpen the invariant and proofExplore the proofHide the proof
Folding the carry into the loop condition (... or carry) is the move that makes the algorithm correct and compact: it handles unequal lengths and the final overflow bit in the same loop, with no special-case code after it. The % 2 / ÷ 2 split is just binary addition's column rule.
ComplexityO(max(m, n)) time, O(max(m, n)) space — One pass produces max(m, n) bits (plus possibly one carry bit), each step O(1). Time O(max(m, n)); the result buffer is O(max(m, n)) space. No conversion, no overflow.
E · Edge cases and pitfalls8a = "1", b = "1" — One column gives bit 0 carry 1; the carry-only iteration adds bit 1 → "10". Tests the carry-in-condition.Explore edge casesHide edge cases
Edge cases handled
a = "1", b = "1"One column gives bit 0 carry 1; the carry-only iteration adds bit 1 → "10". Tests the carry-in-condition.a = "0", b = "0"total = 0, bit 0, carry 0 → buffer "0", reversed "0". No spurious leading zero.a = "1111", b = "1"Carry ripples through all four columns then emits a 5th bit → "10000". Result one longer than the longer input.Very unequal lengthsThe shorter pointer goes negative early; its bit is treated as 0 while the longer string drains — handled by the i>=0 / j>=0 guards.
Pitfalls
- Dropping the final carry — stopping when both strings end returns "0" for "1"+"1".
- Concatenating to an immutable String per column — O(n²); use StringBuilder / list.
- Forgetting to reverse — you'd output the bits most-significant-last.
- Converting chars without `- '0'` / `int()` — adds ASCII codes (e.g. 49) instead of bit values.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic String addBinary(String a, String b) { StringBuilder sb = new StringBuilder(); int i = a.length() - 1, j = b.length() - 1, carry = 0; while (i >= 0 || j >= 0 || carry > 0) { int total = carry;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Dropping the final carry
After both strings are consumed a carry may remain (e.g. 1+1 → bit 0, carry 1). If the loop condition ignores the carry, that most-significant bit is lost and "1"+"1" wrongly returns "0".
Explore the code comparisonHide the code comparison
Dropping the final carry
After both strings are consumed a carry may remain (e.g. 1+1 → bit 0, carry 1). If the loop condition ignores the carry, that most-significant bit is lost and "1"+"1" wrongly returns "0".
Don't write this
while i >= 0 or j >= 0: # carry ignored
total = carry
if i >= 0: total += int(a[i]); i -= 1
if j >= 0: total += int(b[j]); j -= 1
result.append(str(total % 2))
carry = total // 2
# leftover carry never emittedWrite this instead
while i >= 0 or j >= 0 or carry: # carry keeps the loop alive
total = carry
if i >= 0: total += int(a[i]); i -= 1
if j >= 0: total += int(b[j]); j -= 1
result.append(str(total % 2))
carry = total // 22Parsing to a fixed-width integer
Inputs can be 10⁴ bits; Long.parseLong overflows past 63 bits, so the sum is wrong (or throws) for long inputs.
Explore the code comparisonHide the code comparison
Parsing to a fixed-width integer
Inputs can be 10⁴ bits; Long.parseLong overflows past 63 bits, so the sum is wrong (or throws) for long inputs.
Don't write this
long x = Long.parseLong(a, 2);
long y = Long.parseLong(b, 2);
return Long.toBinaryString(x + y);Write this instead
StringBuilder sb = new StringBuilder();
int i = a.length()-1, j = b.length()-1, carry = 0;
while (i >= 0 || j >= 0 || carry > 0) {
int total = carry;
if (i >= 0) total += a.charAt(i--) - '0';
if (j >= 0) total += b.charAt(j--) - '0';
sb.append(total % 2);
carry = total / 2;
}
return sb.reverse().toString();3O(n²) string building
Prepending a char to an immutable String each column copies the whole string every time, giving quadratic time. Append to a mutable buffer and reverse once.
Explore the code comparisonHide the code comparison
O(n²) string building
Prepending a char to an immutable String each column copies the whole string every time, giving quadratic time. Append to a mutable buffer and reverse once.
Don't write this
String res = "";
res = (total % 2) + res; // recreates the whole string each columnWrite this instead
StringBuilder sb = new StringBuilder();
sb.append(total % 2); // O(1) amortised; reverse at the endRevise
Carry the pattern into the interview
Pattern to remember
Right-to-left digit addition with carry
Code pattern to memorize
i, j, carry = len(a)-1, len(b)-1, 0
while i >= 0 or j >= 0 or carry:
total = carry
if i >= 0: total += a[i]; i -= 1
if j >= 0: total += b[j]; j -= 1
append(total % 2) # this column's bit
carry = total // 2 # 0 or 1 into next column
reverse(result)Rules to remember
- 1Loop while
i >= 0 OR j >= 0 OR carry != 0— the trailing carry is its own termination condition ("1"+"1" = "10"). - 2Per column the bit is
total % 2and the next carry istotal // 2—totalis 0..3, so carry is always 0 or 1. - 3Don't parse to int — up to 10⁴ bits overflows 32/64-bit integers; simulate digit by digit.
- 4Build the result reversed (you produce least-significant bit first) and reverse once at the end.
- 5Use a mutable buffer (StringBuilder / list) — appending to an immutable String per column is O(n²).
- 6Convert chars with
c - '0'(Java) /int(c)(Python); append digits as'0'/'1'orstr(bit).
Use this pattern when
- Add / subtract numbers given as strings or digit arrays of arbitrary length
- The values can exceed native integer width (big-number arithmetic)
- Any base-b addition where you process columns right-to-left with a carry
- Linked-list or array 'add two numbers' style problems
Choose another pattern when
- Inputs fit safely in a 64-bit int and the language won't overflow → just parse, add, format (but interviewers usually forbid this)
- You need bitwise tricks on a single fixed-width integer → that's masking/shifting, not string addition
- Multiplication or division of big numbers → different (longer) algorithms
Interview takeaway
Add Binary is the canonical 'simulate arithmetic on strings' problem: one right-to-left pass, a single carry, and a loop condition that includes the carry. The exact same skeleton handles Add Two Numbers (linked lists), Plus One, Add Strings (base 10), and Multiply Strings — change the base and the digit decoding, keep the carry.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternRight-to-left digit simulation with a carry. Whenever numbers arrive as strings, digit arrays, or linked lists — especially when they may exceed native integer width — add column by column from the least-significant end, emitting value % base and carrying value / base, with the carry folded into the loop condition. Same skeleton as Add Two Numbers, Add Strings, Plus One, and Multiply Strings.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Add Two NumbersComing soonSame carry simulation but digits are nodes of a linked list (already least-significant first), base 10.
- Add StringsComing soonIdentical skeleton in base 10 — total = digitA + digitB + carry, emit total % 10, carry total / 10.
- Plus OneComing soonAdd 1 to a digit array with carry propagation; a degenerate single-operand version of this pattern.
- Multiply StringsComing soonExtends digit simulation to multiplication — column products plus carries into a result buffer.