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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Add Binary and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →