Leetcode 67 Add Binary

Problem description

Leetcode 67

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

Process

Binary addition works just like decimal addition: when the sum of two bits exceeds 1, we carry over to the next position. We can iterate from the end of both strings (the least significant bits) while maintaining a carry variable.

For each step:

• Sum the current bits: Add a[i], b[i] (if available), and the carry.

• Update result and carry:

  • Current bit = (a_i + b_i + carry) % 2

  • New carry = (a_i + b_i + carry) // 2

Here, % 2 extracts the remainder (the bit value), while // 2 determines whether we have a carry for the next position.

Example reasoning:

• When the sum equals 2 → bit = 0, carry = 1

• When the sum equals 1 → bit = 1, carry = 0

• When the sum equals 0 → bit = 0, carry = 0

After processing all digits, reverse the result list to get the final binary string.

Code

class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        idxA = len(a) - 1
        idxB = len(b) - 1
        res = []
        carry = 0

        while idxA >= 0 or idxB >= 0 or carry == 1:
            if idxA >= 0:
                carry += int(a[idxA])
                idxA -= 1
            if idxB >= 0:
                carry += int(b[idxB])
                idxB -= 1
            res.append(str(carry%2))
            carry = carry // 2
        return "".join(res[::-1])