67. Add Binary

public class Solution {
    public string AddBinary(string a, string b) {
        int n = a.Length, m = b.Length;
        if (n < m)
            return AddBinary(b, a);
        StringBuilder sb = new StringBuilder();
        int carry = 0, j = m - 1;
        for (int i = n - 1; i >= 0; --i) {
            if (a[i] == '1')
                ++carry;
            if (j > -1 && b[j--] == '1')
                ++carry;
            sb.Append((carry % 2).ToString());
            carry /= 2;
        }
        if (carry == 1)
            sb.Append('1');
        char[] charArray = sb.ToString().ToCharArray();
        Array.Reverse(charArray);
        return new string(charArray);
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string AddBinary(string a, string b) {
        int n = a.size(), m = b.size();
        if (n < m)
            return AddBinary(b, a);
        StringBuilder sb = new StringBuilder();
        int carry = 0, j = m - 1;
        for (int i = n - 1; i >= 0; --i) {
            if (a[i] == '1')
                ++carry;
            if (j > -1 && b[j--] == '1')
                ++carry;
            sb.Append((carry % 2).ToString());
            carry /= 2;
        }
        if (carry == 1)
            sb.Append('1');
        char[] charArray = sb.ToString().ToCharArray();
        Array.Reverse(charArray);
        return new string(charArray);
    }
}

class Solution {
    public String addBinary(String a, String b) {
        int n = a.length(), m = b.length();
        if (n < m) return addBinary(b, a);

        StringBuilder sb = new StringBuilder();
        int carry = 0, j = m - 1;
        for (int i = n - 1; i > -1; --i) {
            if (a.charAt(i) == '1') ++carry;
            if (j > -1 && b.charAt(j--) == '1') ++carry;

            if (carry % 2 == 1) sb.append('1');
            else sb.append('0');

            carry /= 2;
        }
        if (carry == 1) sb.append('1');
        sb.reverse();

        return sb.toString();
    }
}

var addBinary = function (a, b) {
    let n = a.length,
        m = b.length;
    if (n < m) return addBinary(b, a);

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

        result.push((carry % 2).toString());
        carry = Math.floor(carry / 2);
    }
    if (carry === 1) result.push("1");
    return result.reverse().join("");
};

class Solution:
    def addBinary(self, a, b) -> str:
        n = max(len(a), len(b))
        a, b = a.zfill(n), b.zfill(n)

        carry = 0
        answer = []
        for i in range(n - 1, -1, -1):
            if a[i] == "1":
                carry += 1
            if b[i] == "1":
                carry += 1

            if carry % 2 == 1:
                answer.append("1")
            else:
                answer.append("0")

            carry //= 2

        if carry == 1:
            answer.append("1")
        answer.reverse()

        return "".join(answer)

func addBinary(a string, b string) string {
    n, m := len(a), len(b)
    if n < m {
        return addBinary(b, a)
    }

    var result strings.Builder
    carry, j := 0, m-1
    for i := n - 1; i >= 0; i-- {
        if a[i] == '1' {
            carry++
        }
        if j >= 0 && b[j] == '1' {
            carry++
        }
        j--
        result.WriteByte('0' + byte(carry%2))
        carry /= 2
    }
    if carry == 1 {
        result.WriteByte('1')
    }
    s := result.String()
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return string(runes)
}

Algorithm

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, добавьте его. Теперь переreturn строку ответа, и Problema выполнена.

😎