Sponsored
Sponsored
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.
1public class AddBinary {
2
In this Java solution, the Integer.parseInt method is used to convert binary strings to integers. The integers are added and the result is converted back to binary using Integer.toBinaryString.