How do you approach Add Binary?

Walk both strings from the right, exactly as you would add on paper.

What is the time complexity of Add Binary?

Time complexity: O(max(m, n)). Space complexity: O(max(m, n)) for the output..

What are common mistakes on Add Binary?

Building the result with repeated concatenation in a loop - quadratic in most languages; collect into a list and join, or use a string builder. Assuming one character is one code unit. Non-ASCII input breaks index arithmetic. Comparing strings or boxed characters by reference rather than by value.

gitGood.dev

← Back to problems

Add Binary

EasyAlgorithms

Description

Given two binary strings `a` and `b`, return their sum as a binary string. The inputs can be far longer than any built-in integer type, so converting to a number and back is not a viable strategy.

Example 1

Input: a = "11", b = "1"

Output: "100"

Example 2

Input: a = "1010", b = "1011"

Output: "10101"

Example 3

Input: a = "0", b = "0"

Output: "0"

Constraints

- 1 <= a.length, b.length <= 10^4 - Strings consist only of '0' and '1', with no leading zeros except the value "0" itself - Do not convert the whole string to an integer type.

Add Binary: approach, complexity and pitfalls

An easy strings problem, graded against 6 test cases (3 of them hidden).

The pattern: Strings

Parsing, comparison, and character-frequency reasoning.

Reach for it when you see: String input where the work is scanning, comparing, or counting characters.

More Stringsproblems →

If you are stuck

Show the 3-step hint ladder

Walk both strings from the right, exactly as you would add on paper.
At each position add the two digits plus the carry; the output digit is the sum modulo 2 and the new carry is the sum divided by 2.
Keep looping while EITHER string has digits left or the carry is non-zero - the final carry is what turns 11 + 1 into 100.

The optimal approach

Show the approach: Schoolbook addition, base 2

The framing matters: with inputs up to 10^4 digits, no integer type can hold these values, so parsing to a number is not an option. (This is why the problem exists - the one-liner using big integers sidesteps the exercise entirely.)

So add digit by digit from the right, carrying. At each position, `sum = digitA + digitB + carry`; the emitted digit is `sum % 2` and the new carry is `sum / 2` (which in binary is just "was the sum at least 2").

The loop condition is the part that gets fumbled. It must continue while either string has digits remaining or the carry is non-zero - treating a missing digit as 0. Stopping when the shorter string runs out truncates the answer, and stopping before flushing the carry turns `"11" + "1"` into `"00"` instead of `"100"`.

Building the result back-to-front means appending to an array and reversing at the end, rather than prepending to a string - prepending is O(n) per operation and makes the whole thing quadratic.

Time: O(max(m, n))
Space: O(max(m, n)) for the output.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Strings mistakes

These apply to the pattern as a whole, not just this problem.

Building the result with repeated concatenation in a loop - quadratic in most languages; collect into a list and join, or use a string builder.
Assuming one character is one code unit. Non-ASCII input breaks index arithmetic.
Comparing strings or boxed characters by reference rather than by value.