67. Add Binary

Description

Given two binary strings a and b, return their sum as a binary string. The input strings are non-empty and contain only characters 1 or 0.

Intuition

The problem is essentially about adding two binary numbers. Similar to how we add two decimal numbers digit by digit from right to left, we can add two binary numbers bit by bit from right to left, keeping track of the carry.

Approach

1. Initialize Variables: - Use a StringBuilder to construct the result string. - Use an integer carry to store the carry-over during addition. - Use indices i and j to traverse the binary strings a and b from the end to the beginning.
2. Traverse and Add: - While there are bits to process in either string or there is a carry-over: - Add the bits from a and b at positions i and j respectively to the carry. - Append the least significant bit of the carry to the result. - Update the carry to be the remaining part after extracting the least significant bit.
3. Handle Remaining Carry: - If there is any carry left after processing all bits, append it to the result.
4. Construct the Final Result: - The StringBuilder contains the result in reverse order, so reverse it before converting to a string.

Complexity

Time Complexity:

(O(\max(n, m))), where n and m are the lengths of the binary strings a and b, respectively. This is because we traverse both strings once.

Space Complexity:

(O(\max(n, m))), which is the space used to store the result.

Code

C++

class Solution {
public:
    string addBinary(string a, string b) {
        string result = "";
        int carry = 0;
        int i = a.size() - 1, j = b.size() - 1;
        while (i >= 0 || j >= 0 || carry == 1) {
            carry += (i >= 0) ? a[i--] - '0' : 0;
            carry += (j >= 0) ? b[j--] - '0' : 0;
            result = char(carry % 2 + '0') + result;
            carry /= 2;
        }
        return result;
    }
};

Python

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        result = []
        carry = 0
        i, j = len(a) - 1, len(b) - 1
        while i >= 0 or j >= 0 or carry:
            if i >= 0:
                carry += int(a[i])
                i -= 1
            if j >= 0:
                carry += int(b[j])
                j -= 1
            result.append(str(carry % 2))
            carry //= 2
        return ''.join(result[::-1])

Java

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder result = new StringBuilder();
        int carry = 0;
        int i = a.length() - 1, j = b.length() - 1;

        while (i >= 0 || j >= 0 || carry == 1) {
            carry += (i >= 0) ? a.charAt(i--) - '0' : 0;
            carry += (j >= 0) ? b.charAt(j--) - '0' : 0;
            result.append(carry % 2);
            carry /= 2;
        }
        return result.reverse().toString();
    }
}

JavaScript

var addBinary = function(a, b) 
{
    let sum = BigInt('0b'+a)+BigInt('0b'+b)
    return sum.toString(2)
};