Add Strings

Условие

Даны две непустые строки, представляющие собой неотрицательные целые числа num1 и num2. Числа представлены в виде строк, и требуется вернуть их сумму, также в виде строки. Нельзя использовать встроенные функции для работы с большими числами или прямое преобразование строки в целое число.

Примеры

Input: num1 = “11”, num2 = “123”

Output: “134”

Input: num1 = “456”, num2 = “77”

Output: “533”

Input: num1 = “0”, num2 = “0”

Output: “0”

Решение

fun addStrings(num1: String, num2: String): String {
    val result = StringBuilder()
    var carry = 0  // Перенос для сложения
    var i = num1.length - 1
    var j = num2.length - 1

    // Проходим по цифрам с конца обеих строк
    while (i >= 0 || j >= 0 || carry != 0) {
        val x = if (i >= 0) num1[i] - '0' else 0  // Получаем цифру из num1 или 0, если индекс отрицательный
        val y = if (j >= 0) num2[j] - '0' else 0  // Получаем цифру из num2 или 0, если индекс отрицательный

        val sum = x + y + carry  // Сумма цифр и переноса
        result.append(sum % 10)  // Добавляем младший разряд в результат
        carry = sum / 10  // Обновляем перенос

        i--
        j--
    }

    return result.reverse().toString()  // Переворачиваем строку для получения корректного результата
}

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

O(max(n, m)), где n и m — длины строк num1 и num2, так как мы проходим по каждой строке один раз с конца.

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

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