# Билет 04 — рабочий лист

## Условие

Даны две бинарные строки `a` и `b`. Верните их сумму как бинарную строку. Преобразовывать строки в целые числа и обратно встроенными средствами нельзя (длины до 10^4, в языках с фиксированной длиной — переполнение; условие прямо запрещает).

```
Input: a = "11",   b = "1"    →  Output: "100"
Input: a = "1010", b = "1011" →  Output: "10101"
```

Constraints: `1 <= a.length, b.length <= 10^4`; строки состоят только из `'0'` и `'1'`; ведущих нулей нет (кроме самой строки `"0"`).

## Решение — пиши здесь

```ruby
#
# Твоя реализация. Не забудь: проговаривай (пиши в комментариях) —
# 1) идею, 2) сложность по времени, 3) сложность по памяти,
# 4) граничные случаи.
#

def add_binary(a, b)
  result = Array.new([a.size, b.size].max + 1, 0)

  a_pos = a.size - 1
  b_pos = b.size - 1
  pos = result.size - 1

  while a_pos >= 0 || b_pos >= 0 do
    num1 = a_pos >= 0 ? a[a_pos].to_i : 0
    num2 = b_pos >= 0 ? b[b_pos].to_i : 0

    p1 = pos - 1
    p2 = pos

    sum = result[p2] + num1 + num2
    result[p2] = sum % 2
    result[p1] = sum / 2

    a_pos -= 1
    b_pos -= 1
    pos -= 1
  end

  while result.first == 0 && result.size > 1
    result.shift
  end

  result.map(&:to_s).join
end
```

time: O(n)
mem: O(1)