Intuition

The idea is to traverse both strings from the back while keeping track of a carry. At each step, we compute the binary sum of the two digits along with the carry using a helper function. This function returns both the result of the current binary addition and the new carry.

⚠️ Using the BigInt class could solve this problem instantly, but during an interview, demonstrating a logical approach without built-in functions is expected.
Just for your reference: return (BigInt('0b'+a) + BigInt('0b'+b)).toString(2);

Approach

1. Initialize carry = '0' and two pointers i and j at the end of both strings.

2. Traverse both strings from the back until it goes out of bounds ( less than 0).

3. Get current digits (default to '0' if out of bounds).

4. Compute binary sum and carry using binaryEval which uses no of 1 from parameters.

5. Prepend sum to result, update carry, and decrement pointers.

6. After the loop, prepend carry if non-zero and return the result.

Complexity

• Time complexity:
  We traverse both strings once, so the time complexity is O(max(N,M))
  where N and M are the lengths of the two input strings.

• Space complexity:
  We store the result in a string, which can be at most O(max(N,M)) in size.
  Apart from that, only a few extra variables are used, making it O(1) auxiliary space.

Code

JavaScript

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    let carry = '0';
    let i = a.length - 1, j = b.length - 1;
    let result = '';

    /* loop exits only when both pointers are exhausted */
    while (i >= 0 || j >= 0) {
        /* assign 0 as default value if pointers are exhausted (out of bounds)*/
        const n1 = i >= 0 ? a[i] : '0';
        const n2 = j >= 0 ? b[j] : '0';

        let [currentResult, currentCarry] = binaryEval(n1, n2, carry);        
        /* prepend the current binary value and assign latest carry */
        result = currentResult + result;
        carry = currentCarry;

        i--;
        j--;
    }

    if (carry === '1') result = carry + result;

    return result;
};

/**
 * Evaluates binary sum and carry for given bits.
 * @param {string} a 
 * @param {string} b 
 * @param {string} carry 
 * @return {[string, string]}
 */
const binaryEval = function(a, b, carry) {
    let result = ['0', '0'];
    let ones = 0;

    if (a === '1') ones++;
    if (b === '1') ones++;
    if (carry === '1') ones++;

    if (ones % 2 === 1) result[0] = '1';    /* result is 1 incase of 1 or 3 ones */
    if (ones > 1) result[1] = '1';          /* carry is 1 when there are more than 1 ones */

    return result;
};