Add Binary
Asked at Walmart
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Walmart | Easy | View all Walmart 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.
Visual walkthrough for a = "11", b = "1":
Position 1 (rightmost): 1 + 1 + carry(0) = 2. digit = 0, carry = 1.
Position 0: 1 + 0 (b is shorter) + carry(1) = 2. digit = 0, carry = 1.
Remaining carry: 1.
Result: "100" (read in reverse).
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.
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Add Binary?
Add Binary is asked at Walmart. 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.