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

Approaches

Bit By Bit

Explanation

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__bit_by_bit import addBinary
>>> addBinary('11', '1')
'100'
>>> addBinary('1010', '1011')
'10101'

Complexity

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

Measure	Complexity	Notes
Time	\(O(\max(m, n))\)	single pass through the bits
Auxiliary Space	\(O(1)\)	only the carry bit

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

Add two binary numbers a and b.