Skip to main content

67. Add Binary

easy

Add two binary strings and return their sum as a binary string. A textbook digit-by-digit carry-propagation problem — the binary analog of grade-school addition.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given two binary strings a and b, return their sum as a binary string.

Constraints

  • 1 <= a.length, b.length <= 10^4
  • a and b consist only of '0' or '1' characters.
  • Each string does not contain leading zeros except for the zero itself.

Examples

Example 1

Input
a = "11", b = "1"
Output
"100"

Example 2

Input
a = "1010", b = "1011"
Output
"10101"

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Walk both strings from the right, just like adding numbers on paper. Maintain a carry bit.

Hint 2

At each position, sum = (digit_a) + (digit_b) + carry. The output digit is sum % 2; the new carry is sum / 2.

Hint 3

Continue while either string has digits left OR carry is non-zero. The last condition matters when '1' + '1' overflows the longer string.

Hint 4

Don't be tempted to int(a, 2) + int(b, 2) — the constraints allow strings up to 10000 bits long, exceeding any built-in int type without bignum support.

Solution approach

Reveal approach

Two pointers i = a.length - 1 and j = b.length - 1, plus a carry bit initialized to 0. Loop while i >= 0 or j >= 0 or carry > 0: sum = carry; if i >= 0 sum += a[i] - '0' and decrement i; if j >= 0 sum += b[j] - '0' and decrement j. Push (sum % 2) onto the front of the output string (or append and reverse at the end) and set carry = sum / 2. Return the assembled string. O(max(m, n)) time, O(max(m, n)) space for the output. The 'or carry > 0' condition is what handles the final overflow bit like 11 + 1 = 100.

Complexity

Time
O(max(m, n))
Space
O(max(m, n))

Related patterns

  • math
  • two-pointers
  • string-scan

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Apple
  • Facebook

More Math practice problems

See all Math problems →