Add Binary
Add two binary strings with two pointers from the right and a carry: each column's sum mod 2 is the bit, sum / 2 the carry.
Problem Understanding
Add Binary: given two binary strings a and b, return their sum as a binary string.
Examples: "11" + "1" = "100", and "1010" + "1011" = "10101".
The Intuition: Column Addition in Base 2
Add the numbers the way you would on paper, right to left:
- Point
iandjat the last bit of each string. - A column's total is the carry plus the bits there, at most
1 + 1 + 1 = 3. - The bit to write is
total % 2, and the carry into the next column istotal / 2. - When one string runs out, treat its bits as 0; when both run out, a leftover carry still adds a bit.
It is the two pointers idea run from the ends of two strings at once. Multiply Strings uses the same right-to-left carry, with every digit pair instead of one column.
Interactive Walkthrough
a and b are right-aligned above the sum, with the carry shown over the next column. Try Carry chain to watch one carry ripple through every column and create a new bit.
Dry Run Table
Input: a = "1010", b = "1011"
| Column | a bit | b bit | carry in | total | write | carry out |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 0 | 2 | 0 | 1 |
| 2 | 0 | 0 | 1 | 1 | 1 | 0 |
| 3 | 1 | 1 | 0 | 2 | 0 | 1 |
| 4 | — | — | 1 | 1 | 1 | 0 |
Answer: written right to left 1, 0, 1, 0, 1, reversed: "10101".
The Solution Template
One loop that runs while either string has bits or a carry is left. C fills a buffer from the end and then shifts the answer to the front so the returned pointer can be freed.
Add Binary Code
1var addBinary = function(a, b) {2 let i = a.length - 1, j = b.length - 1, carry = 0;3 const out = [];4 while (i >= 0 || j >= 0 || carry) {5 let total = carry;6 if (i >= 0) total += Number(a[i--]);7 if (j >= 0) total += Number(b[j--]);8 out.push(total % 2);9 carry = Math.floor(total / 2);10 }11 return out.reverse().join('');12};
Edge Cases & Common Mistakes
- Final carry:
"1" + "1"is"10"; keep looping while the carry is 1. - Different lengths: once a string is used up, add only the other bit and the carry.
- Both zero:
"0" + "0"is"0", a single column with no carry. - Building the string by prepending: prepending to a string each column is O(n²); append, then reverse once.
- Parsing with
int(a, 2): works in Python, but not in languages with fixed-width integers.
Summary
Walk both strings from the right with a carry. Each column writes total % 2 and carries total / 2; keep going while either string has bits or the carry is 1. Reverse the written bits. O(max(m, n)) time and space.
More practice: DSA interview questions with answers · patterns cheat sheet