67.Add_Binary_(Easy).md

67. Add Binary (Easy)

Date and Time: Jul 3, 2024, 22:25 (EST)

Link: https://leetcode.com/problems/add-binary/

Question:

Given two binary strings a and b, return their sum as a binary string.

Example 1:

Input: a = "11", b = "1"

Output: "100"

Explanation: a, b are binary representation, so a + b = 100 in binary.

Example 2:

Input: a = "1010", b = "1011"

Output: "10101"

Edge case 1:

Input: a = "1011", b = "11"

Output: "1110"

Edge case 2:

Input: a = "1011", b = "1011"

Output: "10110"

KeyPoints:

For sure that we need to first reverse a, b then to perform addiction to check if total = 3, which means carry = 1, so we add the current result by str(total % 2) to res, then get the carry by total // 2.

We used ord(a[i]) - ord("0") to get a[i] in binary.

Exampe 1: 11 + 1 = 001 -> 100; Edge case 1: 1101 + 11 = 0111 -> 1110.

My Solution:

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        a, b = a[::-1], b[::-1]
        carry = 0
        res = ""
        for i in range(max(len(a), len(b))):
            new_A = ord(a[i]) - ord("0") if i < len(a) else 0
            new_B = ord(b[i]) - ord("0") if i < len(b) else 0
            total = new_A + new_B + carry
            res += str(total % 2)   # From 0-3
            carry = total // 2 # carry = 1 if total >= 2 else 0
        # If the last digit has a carry
        if carry:
            res += "1"
        return res[::-1]

Time Complexity: $O(n)$
Space Complexity: $O(n)$