Add Binary

Лёгкая№67по битам

Даны два двоичных числа строками из 0 и 1, возможно, разной длины. Нужно вернуть их сумму тоже двоичной строкой. Наш пример: a = "1101" и b = "111" — ответ "10100", то есть 13 + 7 = 20.

67 Add BinaryРазбор · 1×

Пример: a = "1101", b = "111". Сложение столбиком справа налево; верхний ряд — перенос в каждый столбец.

carrya1101= 13b111= 7out—
ещё не сложилитекущий столбец; только что записанная цифрауже сложено; известный переностолько что полученный перенос в следующий столбецсумма

i и j начинают с последних цифр, младших битов: a[3] = 1 и b[2] = 1

01/39
сначала · назад · пуск · шаг
Скорость
1function addBinary(a, b):
2 i = len(a) - 1; j = len(b) - 1
3 carry = 0; out = ""
4 while i >= 0 or j >= 0 or carry == 1:
5 sum = carry
6 if i >= 0: sum = sum + a[i]
7 if j >= 0: sum = sum + b[j]
8 out = (sum & 1) + out
9 carry = sum >> 1
10 i = i - 1; j = j - 1
11 return out
состояние
i
3
j
2
carry
–
sum
–
out
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. В столбце складываются не больше трёх единиц: две цифры и перенос, поэтому sum равно 0, 1, 2 или 3, то есть 00, 01, 10 или 11. Младший бит, sum & 1, — цифра ответа, а бит над ним, sum >> 1, — перенос.
  2. Число, которое кончилось, просто прибавляет 0, поэтому длины a и b могут быть любыми, и короткое не нужно дополнять нулями.
  3. Цикл идёт и пока carry = 1: в нашем примере последний перенос становится старшей единицей, и ответ на цифру длиннее обоих чисел.

Сложность

Время O(n + m): один проход по цифрам a и b и самое большее ещё один столбец для последнего переноса. Память O(max(n, m)) на сам ответ; остальное — несколько чисел.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.