LeetCode 989: Add to Array-Form of Integer

Problem Restatement

We are given an integer num in array form.

That means each element of num is one digit, ordered from most significant to least significant.

For example:

num = [1, 3, 2, 1]

represents:

1321

We are also given an integer k.

We need to return the array-form of:

num + k

The official constraints include 1 <= num.length <= 10^4, each digit is between 0 and 9, num has no leading zeros except zero itself, and 1 <= k <= 10^4.

Input and Output

Function shape:

def addToArrayForm(num: list[int], k: int) -> list[int]:
    ...

Examples

Example 1:

num = [1, 2, 0, 0]
k = 34

The array represents 1200.

Then:

1200 + 34 = 1234

Answer:

[1, 2, 3, 4]

Example 2:

num = [2, 7, 4]
k = 181

The array represents 274.

Then:

274 + 181 = 455

Answer:

[4, 5, 5]

Example 3:

num = [2, 1, 5]
k = 806

The array represents 215.

Then:

215 + 806 = 1021

Answer:

[1, 0, 2, 1]

First Thought: Convert to Integer

A simple solution is to convert the digit array into an integer, add k, then convert the result back to an array.

class Solution:
    def addToArrayForm(self, num: list[int], k: int) -> list[int]:
        value = 0

        for digit in num:
            value = value * 10 + digit

        value += k

        return [int(ch) for ch in str(value)]

This is easy to understand.

Problem With Full Conversion

The array can contain up to 10^4 digits.

In many languages, this number is far larger than the built-in integer range.

Python supports large integers, but LeetCode problems should usually be solved in a language-independent way when the input is clearly digit-based.

We should simulate addition the same way we do it by hand.

Key Insight

Addition starts from the least significant digit.

In the array, that is the rightmost digit.

Instead of converting all of num into an integer, we add k into the array from right to left.

At each step:

total = current_digit + k

The new digit is:

total % 10

The remaining carry is:

total // 10

We can reuse k as the carry because after processing one digit, the rest of k still needs to be added to the next higher place.

Algorithm

Start from the last index of num.

Maintain an answer list in reverse order.

While there are digits left in num or k > 0:

1. If there is a current digit, add it to k.
2. The next result digit is k % 10.
3. Append that digit to answer.
4. Update k = k // 10.
5. Move one digit left in num.

Finally, reverse answer.

Correctness

The algorithm processes digits from right to left, starting with the ones place.

At each step, k contains the remaining value that must be added to the current decimal position and all higher positions. When the current digit is added to k, the ones digit of that sum is exactly the result digit for the current position.

The algorithm appends k % 10, which is that correct digit, then replaces k with k // 10, which is the carry and remaining higher-place value.

This matches ordinary decimal addition.

The loop continues until both the original digits are exhausted and no carry remains. Therefore, every digit of the sum is produced exactly once.

Since digits are produced from least significant to most significant, reversing the answer gives the required array-form order.

Complexity

Let n = len(num).

Implementation

class Solution:
    def addToArrayForm(self, num: list[int], k: int) -> list[int]:
        answer = []
        i = len(num) - 1

        while i >= 0 or k > 0:
            if i >= 0:
                k += num[i]

            answer.append(k % 10)
            k //= 10
            i -= 1

        answer.reverse()
        return answer

Code Explanation

We build the answer from right to left:

answer = []
i = len(num) - 1

The loop continues while there is still a digit in num or a remaining carry in k:

while i >= 0 or k > 0:

If a digit exists at position i, add it into k:

if i >= 0:
    k += num[i]

The current result digit is the last decimal digit of k:

answer.append(k % 10)

Then remove that digit and keep the remaining carry:

k //= 10

Move left in the original array:

i -= 1

Because digits were appended in reverse order, reverse before returning:

answer.reverse()
return answer

Testing

def run_tests():
    s = Solution()

    assert s.addToArrayForm([1, 2, 0, 0], 34) == [1, 2, 3, 4]
    assert s.addToArrayForm([2, 7, 4], 181) == [4, 5, 5]
    assert s.addToArrayForm([2, 1, 5], 806) == [1, 0, 2, 1]
    assert s.addToArrayForm([9, 9, 9], 1) == [1, 0, 0, 0]
    assert s.addToArrayForm([0], 10000) == [1, 0, 0, 0, 0]

    print("all tests passed")

run_tests()