Add Binary
Easy · Bit Manipulation · Math · String · Bit Manipulation · Simulation
Problem
You are given two strings a and b, each holding a non-negative integer written in binary (only the characters '0' and '1').
Return their sum, also as a binary string. The inputs can be thousands of digits long, so do the addition digit by digit rather than converting them to a built-in integer type.
Examples
Input: a = "1011", b = "111" Output: "10010"
11 + 7 = 18, which is 10010 in binary. The carry from the top column adds a fifth digit.
Input: a = "0", b = "0" Output: "0"
Zero plus zero is zero, written as a single digit.
Input: a = "1", b = "1" Output: "10"
1 + 1 = 2: write 0 and carry 1 into a new column.
Constraints
- 1 <= len(a), len(b) <= 10^4
- a and b contain only '0' and '1'
- Neither string has leading zeros unless it is exactly "0"
Approaches
- Baseline: pad, then prepend each digit — time O(max(n, m)²), space O(max(n, m))
Follow-up
How would you add k binary strings at once? Keep one carry that can now be larger than 1: each column total is the sum of the k digits plus the carry, the digit is total % 2 and the new carry is total // 2.
Related problems
Start free on Cariara · Coding problems · System design studio
