Add Binary

Problem

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

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 <= 10:sup:`4`

• a and b consist only of '0' or '1' characters.

• Each string does not contain leading zeros except for the zero itself.

Pattern

Math, String, Bit Manipulation, Simulation

Solution

To make the problem easier, reverse the bit strings into least significant bit first order and pad the shorter bit string with 0s. Then, add the bits with the carry. The next bit is the sum modulo 2 and the carry is the sum divided by 2. At the end, if the carry is not 0, add it to the front of the string.

Code

def addBinary(a: str, b: str) -> str:
    """Add two binary numbers ``a`` and ``b``.
    """
    s = ''
    carry = 0

    a = a[::-1]
    b = b[::-1]
    if len(a) < len(b):
        a += '0' * (len(b) - len(a))
    else:
        b += '0' * (len(a) - len(b))

    for i in range(len(a)):
        a_bit = int(a[i])
        b_bit = int(b[i])
        raw_sum = carry + a_bit + b_bit
        next_bit = raw_sum % 2
        carry = raw_sum // 2
        s = str(next_bit) + s

    return s if carry == 0 else '1' + s

Test

>>> from add_binary__approach_1 import addBinary
>>> addBinary('11', '1')
'100'
>>> addBinary('1010', '1011')
'10101'

Complexity

\(m\) and \(n\) are the lengths of the two bit strings.

Time: \(O(\max(m, n))\) — single pass through the bits

Auxiliary Space: \(O(1)\) — only the carry bit

add_binary__approach_1.addBinary(a: str, b: str) → str

Add two binary numbers a and b.