:orphan:

Add Binary
==========

.. highlight:: none

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.

.. highlight:: python

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
----

.. literalinclude:: ../problems/easy/add-binary/add_binary__approach_1.py
    :language: python
    :lines: 10-

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

Complexity
----------
| :math:`m` and :math:`n` are the lengths of the two bit strings.
| Time: :math:`O(\max(m, n))` — single pass through the bits
| Auxiliary Space: :math:`O(1)` — only the carry bit

.. autofunction:: add_binary__approach_1.addBinary