round: 4
ticket_no: 03
source_no: 30
slug: add-binary
topic: Math / String Simulation
difficulty: Easy
leetcode_id: 67
attempted: true
score: 2
verdict: partial
reviewed_at: 2026-09-15
---

# Билет 03 — Add Binary

## Условие (как предъявлено)

Даны две бинарные строки `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"`).

## Ответ

> Дословно из `work-04-add-binary.md` (код как написан):

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

    result[p2] = (result[p2] + num1 + num2) % 2
    result[p1] = (result[p1] + num1 + num2) / 2
  end

  while result.first == 0
    result.shift
  end

  result.map(&:to_s).join
end

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

## Разбор

**Что верно (в идее):**
- Каркас столбика: массив на `max(n,m)+1` разряд, `%2` / `/2` как единицы и перенос, обход справа налево, срезание ведущих нулей — это перенос подхода multiply на сложение, узнаваемо.
- Идея «перенос живёт в p1 текущего шага и подхватывается на следующем как p2» — рабочая: с двумя фиксами (ниже) вариант проходит все тесты, включая строки 10^4.

**Что упущено и ошибки:**
1. ❌ **Бесконечный цикл:** `a_pos`, `b_pos`, `pos` не декрементируются. Проверка: `timeout 3` → exit 124 (убит). Фатальный баг, на интервью — мгновенный fail.
2. ❌ **Формула переноса расщеплена:** единицы считаются от `result[p2] + num1 + num2`, перенос — от `result[p1] + num1 + num2`. Накопленный перенос прошлого шага (лежит в p2) не входит в перенос. Правильно:
   ```
   sum = result[p2] + num1 + num2
   result[p2] = sum % 2
   result[p1] = sum / 2
   ```
   Демонстрация: `"11"+"1"` — перенос в разряд двоек посчитан от 0 вместо 1 → теряется разряд.
3. ❌ **`"0"+"0"` → пустая строка:** `shift` до опустошения массива. Нужен `break if result.size == 1` или ранний `return "0"`.
4. ⚠️ **Память O(1) неверно:** массив результата + строка выхода — O(max(n,m)) дополнительной памяти. Время точнее O(n+m).
5. ⚠️ **Edge cases не названы:** разная длина строк, строки-нули (`"0"+"0"`, `"0"+"1"`), финальный перенос на разряд длиннее (`"1"+"1"→"10"`), пустые — невозможны по constraints.

**Эталонная идея:**
Два указателя с конца строк, `carry`, идём пока `i >= 0 || j >= 0 || carry > 0`; `sum = carry + bit1 + bit2`; кладём `sum % 2`, `carry = sum / 2`; результат собираем в обратном порядке и реверсуем. Условие цикла включает `carry > 0` — это закрывает финальный перенос `"1"+"1"→"10"` без отдельного разряда шире.

**Время:** O(n+m) — один проход по обеим строкам.

**Память:** O(max(n,m)) на выход (+ O(max(n,m)) временно в массиве-варианте; в эталоне — только выход).

**Граничные случаи:** 1) разная длина `"1"+"111"→"1000"` (указатель обгоняет); 2) финальный перенос `"1"+"1"→"10"`, `"111"+"1"→"1000"`; 3) строки-нули `"0"+"0"→"0"`, `"0"+"1"→"1"`; 4) максимум 10^4 — не влезает в Integer, нельзя `to_i(2)`.

**Критерии (финально):** идея ✅ · структура данных ✅ · сложность ⚠️ (время верно, память O(1) вместо O(max(n,m))) · граничные случаи ❌ (в комментариях не названы)

## Пересдача (после фиксов)

Исправлено: формула переноса `sum = result[p2] + num1 + num2` (раньше перенос считался от `result[p1]` без учёта накопления в `p2`); добавлен `pos -= 1` (раньше `p2` каждый шаг оставался одним и тем же разрядом — младшие перетирались, перенос терялся); `shift` с защитой `result.size > 1` (раньше `"0"+"0"` давал пустую строку).

Финальный прогон: 13/13 OK, включая `"1"*10^4 + "1"*10^4 → 10001 символов` и чередующиеся длинные строки.

Не закрыто: память в комментарии — O(1) вместо O(max(n,m)); edge cases не написаны в ответе (назывались устно при разборе). Это удержало оценку на 2.

**Канон сложности:** O(n+m) / O(max(n,m)) — сверить с `complexity-cheat-sheet.md`.

**Разбор задачи:** [`../../algo-solutions/02-extra/06-math-string-simulation/30-add-binary.md`](../../algo-solutions/02-extra/06-math-string-simulation/30-add-binary.md)