---
title: Add Binary
difficulty: Easy
category: String
leetcode_id: 67
revision_count: 1
last_revision: 2026-09-12
---

# Add Binary

> **LeetCode:** [#67](https://leetcode.com/problems/add-binary/)
> **Сложность:** Easy
> **Категория:** String

## Условие

Даны две бинарные строки `a` и `b`. Вернуть их сумму как бинарную строку. Сложение столбиком справа налево с переносом (carry), как при сложении десятичных чисел, только по основанию 2.

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

## Ключевая идея

Идём двумя указателями с конца обеих строк в начало, на каждом шаге складываем два бита + перенос и вычисляем новый перенос делением на 2. Результат собираем в обратном порядке и разворачиваем в конце.

## Оценка сложности

- **Время:** O(n + m), где n, m — длины строк
- **Память:** O(max(n, m)) — на строку результата

## Решение (Ruby)

```ruby
# @param {String} a
# @param {String} b
# @return {String}
def add_binary(a, b)
  i = a.size - 1
  j = b.size - 1
  carry = 0
  result = []

  while i >= 0 || j >= 0 || carry > 0
    sum = carry
    sum += a[i].to_i if i >= 0
    sum += b[j].to_i if j >= 0
    result << (sum % 2).to_s
    carry = sum / 2
    i -= 1
    j -= 1
  end

  result.reverse.join
end
```

## Разбор на примере

```
Input: a = "11", b = "1"

i=1, j=0, carry=0:
  sum = 0 + 1 + 1 = 2 → result="0", carry=1
i=0, j=-1, carry=1:
  sum = 1 + 1 + 0 = 2 → result="00", carry=1
i=-1, j=-1, carry=1:
  sum = 1 → result="001", carry=0

Result: "" + "001" reversed = "100"
```

## Edge Cases

- Одна из строк пустая (по условию может быть, `""` или `"0"`) → цикл обработает вторую строку
- Строки разной длины → указатели независимо доходят до -1
- Переполнение разряда в конце (например, `"1" + "1"` → `"10"`) → условие `|| carry > 0` добавляет старший бит
- Обе строки `"0"` → результат `"0"`
- Очень длинные строки (до 10^4 символов): нельзя конвертировать в Integer — либо переполнение, либо медленно

## Типичные ошибки

- Забывают `|| carry > 0` в условии цикла — теряется финальный перенос (старший бит)
- Собирают результат в прямом порядке и не делают `reverse`
- Пытаются через `to_i(2)` + `to_s(2)` — работает для коротких строк, но LeetCode-границы (10^4 бит) ломают такой подход
- Не обрабатывают разную длину строк — выход за границы
- Инкремент вместо декремента указателей — идут не с конца, а с начала

## Альтернативные подходы

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| **Сложение столбиком с carry** | **O(n + m)** | **O(max(n, m))** | **финальное решение, стандарт для интервью** |
| Через Integer: `(a.to_i(2) + b.to_i(2)).to_s(2)` | O(n + m) | O(n + m) | работает на малых входных данных, но переполняется на 10^4 битах |
| Сначала выровнять строки нулями, потом идти с конца | O(n + m) | O(n) | эквивалентно, чуть больше кода, но без проверок `i >= 0` |

### Ruby built-in (не для интервью)

```ruby
(a.to_i(2) + b.to_i(2)).to_s(2)
```

> **Важно:** на интервью пишут руками. `Integer#to_s(2)` годен только как быстрая проверка результата.

## Заметки после повторения

_Что забыл? Что пошло не так? На чём застрял? Заполни после каждой тренировки._