989.add-to-array-form-of-integer.md

989. Add to Array-Form of Integer

The key idea is to simulate the addition operation performed manually on paper, starting from the least significant digit (rightmost) of the number and moving towards the most significant digit (leftmost). We add the digit from K to the corresponding digit in the array and keep track of any carry.

def addToArrayForm(self, num: List[int], k: int) -> List[int]:
    results = []
    i = len(num) - 1
    carry = 0
    while 0 <= i or 0 < k:
        sum = (num[i] if i >= 0 else 0) + k % 10 + carry
        results.append(sum % 10)
        carry = sum // 10
        k = k // 10
        i -= 1
    if carry:
        results.append(1)
    return results[::-1]

fun addToArrayForm(num: IntArray, k: Int): List<Int> {
    var carry = 0
    var kk = k
    var i = num.size - 1
    val result = LinkedList<Int>()
    while (i >= 0 || kk > 0) {
        val sum = (if (i >= 0) num[i] else 0) + (kk % 10) + carry
        result.addFirst(sum % 10)
        carry = sum / 10
        kk /= 10
        i--
    }
    if (carry > 0) {
        result.addFirst(1)
    }
    return result
}

• Time Complexity: O(max(n, lg k)), lg k is for k division.
• Space Complexity: O(max(n, lg k)).

We can convert the array into number and sum up with k, but it will overflow if the number is pretty long. So we will use the above solution.

fun addToArrayForm(num: IntArray, k: Int): List<Int> {
    var n = 0
    for (i in 0 until num.size) {
        n = n * 10 + num[i]
    }
    var sum = n + k
    val result = LinkedList<Int>()
    while (sum > 0) {
        result.addFirst(sum % 10)
        sum /= 10
    }
    return result
}

Failed Cases

[0]
k = 23

// Pretty long number that will overflow by using `Int` or `Long`
[................................]

[1,2]
k = 99999