Задача: 67. Add Binary
Сложность: easy

Даны две двоичные строки a и b. Верните их сумму в виде двоичной строки.

Пример:

Input: a = "11", b = "1"
Output: "100"

👨‍💻 Алгоритм:

1⃣Начните с переноса carry = 0. Если в числе a наименьший бит равен 1, добавьте 1 к carry. То же самое относится к числу b: если в числе b наименьший бит равен 1, добавьте 1 к carry. В этот момент carry для наименьшего бита может быть равен 0 (00), 1 (01) или 2 (10).

2⃣Теперь добавьте наименьший бит carry к ответу и перенесите старший бит carry на следующий порядковый бит.

3⃣Повторяйте те же шаги снова и снова, пока не будут использованы все биты в a и b. Если остаётся ненулевой carry, добавьте его. Теперь переверните строку ответа, и задача выполнена.

😎 Решение:

function addBinary($a, $b) {
    $n = strlen($a);
    $m = strlen($b);
    if ($n < $m) return addBinary($b, $a);

    $result = [];
    $carry = 0;
    $j = $m - 1;
    for ($i = $n - 1; $i >= 0; --$i) {
        if ($a[$i] === "1") ++$carry;
        if ($j >= 0 && $b[$j] === "1") ++$carry;

        array_push($result, strval($carry % 2));
        $carry = intdiv($carry, 2);
        $j--;
    }
    if ($carry === 1) array_push($result, "1");
    return implode("", array_reverse($result));
}

Ставь 👍 и забирай 📚 Базу знаний