Условие

Даны две двоичные строки a и b, представляющие двоичные числа. Верните их сумму в виде двоичной строки.

Примеры

Input: a = “11”, b = “1” Output: “100”

Input: a = “1010”, b = “1011” Output: “10101”

Решение

fun addBinary(a: String, b: String): String {
    // Результат сложения
    val result = StringBuilder()
    
    // Переменные для прохода по строкам справа налево
    var carry = 0
    var i = a.length - 1
    var j = b.length - 1
    
    // Проходим по строкам пока есть символы или перенос
    while (i >= 0 || j >= 0 || carry != 0) {
        // Если символ есть в строке 'a', преобразуем его в число, иначе 0
        val sumA = if (i >= 0) a[i--] - '0' else 0
        // Если символ есть в строке 'b', преобразуем его в число, иначе 0
        val sumB = if (j >= 0) b[j--] - '0' else 0
        
        // Суммируем текущие символы и перенос
        val sum = sumA + sumB + carry
        
        // Результат текущего разряда (0 или 1)
        result.append(sum % 2)
        
        // Перенос на следующий разряд
        carry = sum / 2
    }
    
    // Разворачиваем строку результата, так как складывали справа налево
    return result.reverse().toString()
}

Временная сложность

O(max(n, m)), где n и m — длины строк a и b.

Пространственная сложность

O(max(n, m)), так как строка для результата требует столько же места, сколько и максимальная из входных строк.