Given two binary strings a and b, return their sum as a binary string.
Example 1:
Input: a = "11", b = "1" Output: "100"
Example 2:
Input: a = "1010", b = "1011" Output: "10101"
Constraints:
1 <= a.length, b.length <= 104a and b consist only of '0' or '1' characters.The Add Binary problem asks you to add two binary numbers represented as strings and return the result as another binary string. Since binary addition follows simple rules (0+0, 0+1, 1+1 with a carry), the most intuitive method is to simulate the manual addition process.
Start from the rightmost digits of both strings and move left while maintaining a carry. At each step, add the corresponding bits along with the carry. The resulting bit is appended to the result, and the new carry is updated accordingly. Using a StringBuilder (or similar structure) helps efficiently construct the result in reverse before reversing it at the end.
An alternative view involves bit manipulation concepts, where binary addition logic mirrors XOR for the sum and AND for the carry. However, since the inputs are strings, the simulation approach is usually the most practical.
This approach processes each digit once, leading to a time complexity of O(n) and space complexity of O(n), where n is the length of the longer binary string.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Binary Addition Simulation (right-to-left traversal) | O(n) | O(n) |
| Bit Manipulation Conceptual Approach | O(n) | O(n) |
NeetCode
This method involves simulating the addition process as if one were adding numbers on paper. We traverse both strings from the least significant bit to the most, adding corresponding bits and maintaining a carry as needed. If the carry is still 1 after processing both strings, it is added to the result.
Time Complexity: O(max(N, M)) where N and M are the lengths of strings a and b. The space complexity is also O(max(N, M)) to store the result.
1#include <iostream>
2#include <string>
3using namespace std;
4
5string addBinary(string a, string b) {
6 string result = "";
7 int carry = 0, i = a.size() - 1, j = b.size() - 1;
8 while (i >= 0 || j >= 0 || carry) {
9 int sum = carry;
10 if (i >= 0) sum += a[i--] - '0';
11 if (j >= 0) sum += b[j--] - '0';
12 result = char(sum % 2 + '0') + result;
13 carry = sum / 2;
14 }
15 return result;
16}
17
18int main() {
19 string a = "1010";
20 string b = "1011";
21 cout << addBinary(a, b) << endl;
22 return 0;
23}This implementation uses the C++ string class, accumulating the final binary result as a string. By working backwards from both input strings and calculating the bitwise addition with a carry, it appends each bit to the resultant string, which is then returned.
This approach leverages built-in support for manipulating large integers available in many programming languages. By converting binary strings to integers, performing arithmetic operations, and then converting the result back to binary format, we can simplify the computation.
Time Complexity: O(N + M), due to integer conversion and addition operations. Space Complexity: O(N + M) for storing integer representations.
1def addBinary(a: str, b:
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Add Binary is a common easy-level interview problem used to test understanding of binary arithmetic, string manipulation, and edge case handling. It often appears as a warm-up question in technical interviews.
The optimal approach is to simulate binary addition from right to left while maintaining a carry value. At each step, add the corresponding bits and the carry, append the resulting bit, and update the carry. This ensures linear time processing of the input strings.
A StringBuilder (or dynamic string structure) is commonly used to build the result efficiently. Since digits are processed from right to left, the result is typically constructed in reverse and then reversed at the end.
Binary addition works like decimal addition where the least significant digits are processed first. Starting from the right allows us to correctly handle carry propagation as we move toward the most significant bits.
This Python solution uses the int function to convert binary strings to integers, adds them, and converts the sum back to binary format using the bin function, stripping the '0b' prefix with slicing.