Add Binary easy

Problem Statement

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"

Steps

  1. Initialization: Initialize a variable result as an empty string to store the binary sum. Also initialize a variable carry to 0. We'll use carry to handle cases where the sum of two bits exceeds 1.

  2. Iteration: Iterate through the strings a and b from their rightmost digits (least significant bits) using a while loop. We'll use pointers i and j to keep track of the current positions in strings a and b respectively.

  3. Bitwise Sum: For each position, calculate the sum of the bits from a and b (convert character to number using parseInt with radix 2), along with the carry from the previous iteration.

  4. Determine Result Bit: The result bit is the remainder when the sum is divided by 2.

  5. Update Carry: The carry for the next iteration is the integer division (quotient) of the sum by 2.

  6. Append Result Bit: Append the result bit (converted back to string) to the beginning of the result string (because we are processing from right to left).

  7. Handle Remaining Bits: After one of the strings is fully processed, continue the loop, processing remaining bits from the other string and the carry.

  8. Final Carry: If there's a remaining carry after the loop finishes, prepend it to the result string.

  9. Return Result: Return the result string.

Explanation

The algorithm simulates binary addition using bitwise operations. The carry variable keeps track of the overflow from each bit addition. The loop processes the strings from right to left (least significant bit to most significant bit), correctly handling the propagation of the carry. Using parseInt(bit, 2) converts a single binary digit character ('0' or '1') to its integer equivalent (0 or 1), and appending the result to the beginning of result reverses the process, building the binary sum correctly.

Code

function addBinary(a: string, b: string): string {
    let i = a.length - 1;
    let j = b.length - 1;
    let carry = 0;
    let result = "";

    while (i >= 0 || j >= 0 || carry) {
        let sum = carry;
        if (i >= 0) sum += parseInt(a[i--], 2);
        if (j >= 0) sum += parseInt(b[j--], 2);

        result = (sum % 2) + result;
        carry = Math.floor(sum / 2);
    }

    return result;
};

Complexity

  • Time Complexity: O(max(m, n)), where m and n are the lengths of strings a and b respectively. The while loop iterates at most max(m, n) + 1 times.

  • Space Complexity: O(max(m, n)). The space used by the result string is proportional to the length of the longer input string. In the worst case, the result string will be one digit longer than the longer input string.