Add Binary Strings

Reported in interviews at Hudson River Trading

Problem statement

You are given two non-empty strings $a$ and $b$, each representing a non-negative integer in binary (every character is '0' or '1'). Return their sum, also as a binary string, with no leading zeros (except that the string "0" itself represents zero).

Write a function with the signature:

def addBinary(a: str, b: str) -> str:

Constraints:

  • $1 \leq |a|, |b| \leq 10^4$
  • Each string consists only of the characters '0' and '1'
  • Neither string has leading zeros, except the string "0" itself

Examples:

  1. addBinary("11", "1") -> "100" (binary $3 + 1 = 4$)
  2. addBinary("1010", "1011") -> "10101" (binary $10 + 11 = 21$)
  3. addBinary("0", "0") -> "0"
Show hint

How would you add two long decimal numbers by hand, column by column?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems