Условие

Дано целое число k и массив num, представляющий собой цифры целого числа в порядке от старшего разряда к младшему. Требуется вернуть массив, представляющий сумму числа, составленного из массива num, и числа k.

Примеры

Input: num = [1,2,0,0], k = 34 Output: [1,2,3,4] Explanation: Число, составленное из массива num, равно 1200. При добавлении 34 получается 1234. Массив результата — [1,2,3,4].

Input: num = [2,7,4], k = 181 Output: [4,5,5] Explanation: Число, составленное из массива num, равно 274. При добавлении 181 получается 455. Массив результата — [4,5,5].

Input: num = [2,1,5], k = 806 Output: [1,0,2,1] Explanation: Число, составленное из массива num, равно 215. При добавлении 806 получается 1021. Массив результата — [1,0,2,1].

Решение

fun addToArrayForm(num: IntArray, k: Int): List<Int> {
    val result = mutableListOf<Int>()
    var carry = k
    var i = num.size - 1

    // Проходим по массиву num с конца к началу
    while (i >= 0 || carry > 0) {
        if (i >= 0) {
            carry += num[i]  // Добавляем текущую цифру из num к carry
            i--
        }
        result.add(carry % 10)  // Добавляем младшую цифру carry к результату
        carry /= 10  // Обновляем carry, удаляя младшую цифру
    }

    result.reverse()  // Переворачиваем результат, чтобы получить правильный порядок цифр
    return result
}

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

O(max(n, log k)), где n — длина массива num, а log k — количество цифр в числе k. Мы проходим по массиву num и числу k одновременно, выполняя операции сложения и переноса.

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

O(max(n, log k)), поскольку результат может содержать до max(n, log k) цифр, включая возможный дополнительный разряд при переносе.