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 <stdio.h>
2#include <string.h>
3
4char* addBinary(char* a, char* b) {
5 static char result[10001];
6 memset(result, 0, sizeof(result));
7 int carry = 0, i = strlen(a) - 1, j = strlen(b) - 1, k = 10000;
8
9 while (i >= 0 || j >= 0 || carry) {
10 int sum = carry;
11 if (i >= 0) sum += a[i--] - '0';
12 if (j >= 0) sum += b[j--] - '0';
13 result[k--] = (sum % 2) + '0';
14 carry = sum / 2;
15 }
16 return result + k + 1;
17}
18
19int main() {
20 char* a = "1010";
21 char* b = "1011";
22 printf("%s\n", addBinary(a, b));
23 return 0;
24}The code declares an array result to hold the final binary string, iterates through the input strings from the end to the start, calculates the bit sum while considering a carry, and builds the result string by adjusting the index with a carry sum. The final output is the result trimmed to exclude leading zeros.
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:
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.