67. Add Binary
Asked at Walmart, Bloomberg
Difficulty
Easy
Time
O(max(m, n))
Space
O(max(m, n))
Pattern
Math
Companies
2
Problem
You are given two strings a and b. Each string holds a binary number written in the usual way: only 0 and 1 characters, most significant bit first, and no extra leading zeros.
Return a new string that holds the sum of those two numbers, also written in binary. The result must have no leading zeros either, except when the answer is zero itself.
You cannot just convert to a normal integer, because the strings can be up to 10^4 characters long. Instead, add the two numbers the way you would by hand: start at the right end, add one column at a time, and pass the carry to the next column on the left.
Add two binary strings column by column
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
a = "11", b = "1""100"a = "1010", b = "1011""10101"Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Walmart | Easy | View all Walmart questions → |
| Bloomberg | Easy | View all Bloomberg questions → |
How to Think About It
Two pointers from the end: start from the last character of both strings. Add the digits along with a carry. The sum can be 0, 1, 2, or 3. If sum >= 2, the carry is 1 for the next position.
The algorithm: use two pointers i and j starting at the end of a and b. While i >= 0 or j >= 0 or carry > 0:
- Get digit from a (0 if i < 0), digit from b (0 if j < 0)
- total = digit_a + digit_b + carry
- digit = total % 2, carry = total // 2
- Prepend digit to result
- Decrement i and j
Why prepend: building the result from right to left means each new digit goes at the front. In Python, use string concatenation or reverse at the end. In C++, use a string and reverse it.
Edge cases: both strings are "0" (return "0"), different lengths (pad shorter with leading zeros conceptually), carry at the most significant bit (adds an extra digit).
Optimal Approach
Step 1: Initialize i = len(a)-1, j = len(b)-1, carry = 0.
Step 2: While i >= 0 or j >= 0 or carry > 0:
- digit_a = int(a[i]) if i >= 0 else 0
- digit_b = int(b[j]) if j >= 0 else 0
- total = digit_a + digit_b + carry
- Prepend str(total % 2) to result
- carry = total // 2
- Decrement i and j
Step 3: Return result.
Walkthrough for a = "1010", b = "1011":
- i=3, j=3: 0+1+0=1. digit=1, carry=0. result="1"
- i=2, j=2: 1+1+0=2. digit=0, carry=1. result="01"
- i=1, j=1: 0+0+1=1. digit=1, carry=0. result="101"
- i=0, j=0: 1+1+0=2. digit=0, carry=1. result="0101"
- carry=1. result="10101"
Time: O(max(m,n)) where m and n are string lengths. Space: O(max(m,n)) for the result.
Two pointers plus a carry
What Trips People Up in Real Interviews
Trying to convert to integers and add. Binary strings can be up to 10^4 characters long, which overflows any integer type. You must simulate addition digit by digit.
Forgetting the final carry. After processing all digits, if carry is still 1, you need to prepend it. For example, "1" + "1" = "10" requires an extra digit from the carry.
Using the wrong index direction. Start from the end (least significant bit) and work backwards. Starting from the beginning gives you the wrong order.
Not handling different string lengths. When one string is shorter, treat the missing digits as 0. Don't pad the strings with leading zeros unless you want to.
Appending digits to the wrong end. Build the result from right to left, so prepend each digit. If you append, you get the result reversed.
Solution Code
O(max(m, n)) timedef addBinary(a, b):
i, j, carry = len(a) - 1, len(b) - 1, 0
result = []
while i >= 0 or j >= 0 or carry:
digit_a = int(a[i]) if i >= 0 else 0
digit_b = int(b[j]) if j >= 0 else 0
total = digit_a + digit_b + carry
result.append(str(total % 2))
carry = total // 2
i -= 1
j -= 1
return ''.join(reversed(result))Frequently Asked Questions
What is the Add Binary problem?
Given two binary strings a and b, return their sum as a binary string. This is a simulation problem that tests your ability to handle string manipulation and carry propagation, similar to adding numbers by hand.
How do you solve Add Binary?
The optimal approach runs in O(max(m, n)) time and O(max(m, n)) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Add Binary?
Add Binary is asked at Walmart, Bloomberg. It is a easy difficulty problem.
What are common mistakes on Add Binary?
- Trying to convert to integers and add. Binary strings can be up to 10^4 characters long, which overflows any integer type. You must simulate addition digit by digit.
- Forgetting the final carry. After processing all digits, if carry is still 1, you need to prepend it. For example, "1" + "1" = "10" requires an extra digit from the carry.
- Using the wrong index direction. Start from the end (least significant bit) and work backwards. Starting from the beginning gives you the wrong order.
- Not handling different string lengths. When one string is shorter, treat the missing digits as 0. Don't pad the strings with leading zeros unless you want to.
- Appending digits to the wrong end. Build the result from right to left, so prepend each digit. If you append, you get the result reversed.