67. Add Binary

Problem

Tags: Math, String, Bit Manipulation, Simulation

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 <= 10^4
• a and b consist only of '0' or '1' characters.
• Each string does not contain leading zeros except for the zero itself.

Code

C

// 67. Add Binary (8/2/54188)
// Runtime: 2 ms (47.22%) Memory: 5.61 MB (76.73%) 

#define MAX(a, b) ((a > b) ? a : b)

char* addBinary (char* a, char* b) {
    int len_a = strlen(a), len_b = strlen(b);
    char* result = (char*)calloc(MAX(len_a, len_b) + 2, sizeof(char));
    
    int carry = 0;
    int idx_a = strlen(a) - 1, idx_b = strlen(b) - 1;
    for (int i = MAX(len_a, len_b); i >= 0; i--) {
        int bit = carry;
        if (idx_a >= 0) bit += a[idx_a--] - '0';
        if (idx_b >= 0) bit += b[idx_b--] - '0';
        carry = bit >> 1;
        result[i] = (bit % 2) + '0';
    }
    
    return result + (result[0] == '0');
}

TS

// 67. Add Binary (7/18/54188)
// Runtime: 76 ms (78.57%) Memory: 45.57 MB (26.89%) 

function addBinary(a: string, b: string): string {
    let big_a = BigInt(0), big_b = BigInt(0);

    for (let i = 0; i < a.length; i++)
        big_a += BigInt(a[i]) << BigInt(a.length - i - 1);
    for (let i = 0; i < b.length; i++)
        big_b += BigInt(b[i]) << BigInt(b.length - i - 1);

    return (big_a + big_b).toString(2);
};