67. Add Binary
You receive two strings a and b. Each one contains only the characters '0' and '1' and spells out a non-negative integer in base 2, most significant bit first. Neither string has leading zeros unless it is exactly "0".
Return the sum a + b, also written as a binary string with no unnecessary leading zeros.
Either operand may be thousands of bits long, so add the strings column by column the way you would on paper — don't rely on converting them to a fixed-width integer type.
Example 1:
Input: a = "101", b = "11"
Output: "1000"
Explanation: In decimal this is 5 + 3 = 8, and 8 in binary is 1000. The carry from the rightmost column ripples across every bit.
Example 2:
Input: a = "10", b = "1"
Output: "11"
Explanation: 2 + 1 = 3, which is 11 in base 2. No column produces a carry here.
Constraints:
- 1 ≤ a.length, b.length ≤ 10⁴
- a and b consist only of the characters '0' and '1'
- Neither string has leading zeros, except the string "0" itself.
Hints:
Binary column addition has only a handful of cases: each column sums 0, 1, 2, or 3 (two bits plus an incoming carry). The written digit is `sum % 2` and the outgoing carry is `sum / 2`.
Start from the last character of each string and walk left with two indices and a carry. Keep looping while either index is alive OR the carry is 1 — forgetting the final carry drops the leading bit of results like 1 + 1 = 10. Build the answer backwards, then reverse it.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: a = "101", b = "11"
Expected output: "1000"