Add Binary
Two non-negative integers are written in base 2 as strings a and b, most significant bit first. Each string contains only the characters '0' and '1', and neither has leading zeros unless the number itself is zero (written as "0").
Return their sum, also as a base-2 string in the same format.
The strings can be thousands of digits long, far beyond any fixed-size integer type, so solve it by adding the digits yourself rather than converting the whole string to a number.
Example 1
Example 2
Example 3
Constraints
1 <= a.length, b.length <= 104aandbconsist only of'0'and'1'.- No leading zeros, except for the number zero itself.
Pattern Path · Math, Bits & Strings · problem 27 of 169
total % 2 and the new carry is total // 2. Do not forget a final carry, and reverse the collected digits at the end.Start simple
Converting both strings to integers and back is O(n) in Python but overflows fixed-width types in most languages; the digit-by-digit method works everywhere in O(max(m, n)).
The key idea
This is grade-school column addition in base 2. Start with two pointers at the last characters (the least significant bits) and a carry of 0.
At each step, add the current bit of a (or 0 if a is exhausted), the current bit of b (or 0) and the carry. The total is between 0 and 3. Its low bit, total % 2, is the output digit for this column, and its high bit, total // 2, carries into the next column. Move both pointers one step left.
Keep going while either string still has digits or the carry is 1; that last condition produces the extra leading digit in cases like 1 + 1 = 10. Digits come out from least to most significant, so collect them in a list and reverse once at the end, which is cheaper than prepending to a string each time.
The method never needs a number larger than 3, so it works for inputs of any length in any language.
Complexity
- Time:
O(max(m, n)) - Space:
O(max(m, n)) for the result
Python
class Solution:
def addBinary(self, a: str, b: str) -> str:
i, j = len(a) - 1, len(b) - 1
carry = 0
digits = []
while i >= 0 or j >= 0 or carry:
total = carry
if i >= 0:
total += int(a[i])
i -= 1
if j >= 0:
total += int(b[j])
j -= 1
digits.append(str(total % 2))
carry = total // 2
return ''.join(reversed(digits))JavaScript
var addBinary = function(a, b) {
let i = a.length - 1;
let j = b.length - 1;
let carry = 0;
const digits = [];
while (i >= 0 || j >= 0 || carry) {
let total = carry;
if (i >= 0) total += a.charCodeAt(i--) - 48; // '0' is 48
if (j >= 0) total += b.charCodeAt(j--) - 48;
digits.push(total % 2);
carry = total >> 1;
}
return digits.reverse().join('');
};What the interviewer is checking
It checks careful loop control: different lengths, a trailing carry, and building the output efficiently instead of relying on big-integer conversion.
Mistakes to avoid
- Forgetting the final carry, so "1" + "1" returns "0" instead of "10".
- Stopping when the shorter string runs out.
- Prepending characters to a string inside the loop, which is quadratic in many languages.
- Parsing the strings into a 32- or 64-bit integer, which overflows for long inputs.
Follow-ups to expect
- Can you do it without the + operator? (XOR for sum, AND shifted for carry.)
- Generalize to any base k. (total % k and total // k.)
- How would you multiply two binary strings? (Shift-and-add over the bits.)
In real software
Arbitrary-precision arithmetic libraries (big integers in cryptography, exact money calculations) add numbers digit block by digit block with a carry in exactly this way.