fun main() {
    println(calculate(listOf(9), listOf(2))) // result=[1, 1]
    println(calculate(listOf(9), listOf(1))) // result=[1, 0]
    println(calculate(listOf(9), listOf(0))) // result=[0, 9] - лидирующий незначащий ноль можно удалить
    println(calculate(listOf(9, 8), listOf(1))) // result=[9,9]
    println(calculate(listOf(9, 9, 9), listOf(1))) // result=[1, 0, 0, 0]
    println(calculate(listOf(9, 9, 8), listOf(1))) // result=[0, 9, 9, 9] - лидирующий незначащий ноль можно удалить
}

// TC: max(O(a.size), O(b.size)) - временная сложность
// SC: max(O(a.size), O(b.size) + 1) - сложность по памяти
fun calculate(a: List<Int>, b: List<Int>): List<Int> {
    // Добавляем 1 к максимальной длине числа, чтобы избавиться от граничащих случаев как a=[1], b=[9]
    // Если не прибавлять 1, то result=[0-сумма 9 + 1], если добавить 1, то result=[1-то что мы запомнили при сложении 9 + 1, 0-сумма 9 + 1]
    val res = ArrayList<Int>()
    // заполняю результирующий массив нулями
    repeat(max(a.size, b.size) + 1) {
        res.add(0)
    }

    // Нет необходимости разворачивать массивы и тратить дополнительную память на аллокацию новых

    // указатель(индекс) на текущую цифру в числе a
    var i = a.size - 1

    // указатель(индекс) на текущую цифру в числе b
    var j = b.size - 1

    // указатель(индекс) для записи результирующей суммы в res(result)
    var k = res.size - 1
    // то что запоминаем в уме, никогда не превышает 1, можно проверить на граничащих случаях 9 + 9 или 999 + 999
    var save = 0
    while (i >= 0 || j >= 0) {
        // если указатель уходит за пределы массива, то дефолтное значение будет 0
        // например a=[1], b=[6,7,8]
        // на первой итерации i = 0(сылается на 1), j = 2(ссылатеся на 8)
        // на второй итерации i = -1(не ссылается на элемент a, поэтому first = 0), j = 1(ссылается на 7)
        val first = a.getOrElse(i) { 0 }
        val second = b.getOrElse(j) { 0 }

        // sum гарантирована находится в диапазоне [0, 19], можно проверить на краевых случаях
        // first=9, second=9, save=1 => sum = 9 + 9 + 1 = 19
        val sum = first + second + save
        // save(то что запоминаем в уме(еще называют carry) можно находить целочисленным делением на 10
        // можно проверить на краевых случаях, так как sum находится в диапазоне [0, 19],то
        // при sum=[0..9] save = 0, так как если (0 <= sum < 10), то деление числа < 10 на 10 дает нам ноль
        // при sum=[10, 19] save = 0, так как если (10 <= sum <= 19), то деление на 10 дает нам 1
        save = sum / 10

        // так как sum=[0..19], то последнее число можно получить остатком деления на 10
        // если sum=[n = 0..9], то result=n % 10 = n
        // если sum=[n = 10..19], то result = n % 10 = последней цифре sum, в случае 10=0, в случае 15=5, и так далее
        val result = sum % 10
        res[k] = result
        i--
        j--
        k--
    }
    // случай, когда сложение двух чисел одинаковой длины может заполнить наш save, но мы выйдем из прошлого цикла
    // Например, a=[9], b=[2], после первой итерации i=-1, j=-1 и мы выходим из цикла выше
    // если не обработать этот кейс, то результат будет result=[0, 1], а ожидается [1,1]
    if (save == 1){
        res[0] = 1
    }
    return res
}