LeetCode 989 - Add to Array-Form of Integer

Difficulty: 🟢 Easy
Topics: Array, Math

Solution

Problem Understanding

The problem is asking us to perform addition between a number represented as an array of digits, num, and an integer k. The array-form of a number represents each digit in left-to-right order, so the first element corresponds to the most significant digit. For example, [1, 2, 0, 0] represents the number 1200.

Given num and k, we are expected to return the array-form of their sum. The output must also be a list of digits in left-to-right order, consistent with the input format.

The constraints tell us that num can be very large, up to 10^4 digits, so converting it directly to an integer could be impractical in languages with fixed-size integers. Similarly, k is constrained to be at most 10^4, so it is relatively small compared to num.

Important edge cases include when k adds a carry that extends the number of digits in num, such as adding 1 to [9, 9, 9], which should yield [1, 0, 0, 0]. Another edge case is when num has only one digit or k is larger than num.

Approaches

A brute-force approach is to first convert the array num into an integer, add k, then convert the result back into an array. This works correctly because addition is associative, but it fails for very large num values due to integer overflow or inefficiency in handling large numbers in some languages.

The optimal approach is to simulate the addition manually, starting from the least significant digit (the end of the array) and adding k digit by digit while managing the carry. The key insight is that k can be processed one digit at a time using modulo and integer division, eliminating the need to convert the entire array to an integer. This approach scales linearly with the number of digits in num and handles large numbers safely.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n + log k)	O(n + log k)	Convert array to integer, add k, then convert back to array
Optimal	O(max(n, log k))	O(max(n, log k))	Process digits from end with carry, construct result in reverse

Algorithm Walkthrough

Initialize an empty list result to store the digits of the sum in reverse order.
Start from the last index of num and iterate backward while i >= 0 or k > 0.
At each step, add the current digit of num (if i >= 0) and the last digit of k (via k % 10) along with any existing carry.
Compute the new digit as total % 10 and append it to result.
Update k as k // 10 to remove the last digit already added.
Move to the previous digit of num by decrementing i.
After the loop, reverse result to obtain the correct order from most significant to least significant digit.

Why it works: At each iteration, we correctly compute the sum of the corresponding digits of num and k along with carry. By iterating from least significant to most significant digit, the carry propagates naturally, guaranteeing correctness. The loop continues until all digits of num and k are processed, ensuring no digits are missed.

Python Solution

from typing import List

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        result = []
        i = len(num) - 1
        
        while i >= 0 or k > 0:
            if i >= 0:
                k += num[i]
            result.append(k % 10)
            k //= 10
            i -= 1
        
        return result[::-1]

The Python implementation follows the optimal algorithm directly. We initialize a result list to store digits in reverse. The loop condition ensures we continue until both num and k are exhausted. Inside the loop, we add the current digit from num to k, extract the last digit, append it to result, and update k by integer division. Finally, we reverse result to get the correct array-form.

Go Solution

func addToArrayForm(num []int, k int) []int {
    result := []int{}
    i := len(num) - 1

    for i >= 0 || k > 0 {
        if i >= 0 {
            k += num[i]
        }
        result = append(result, k%10)
        k /= 10
        i--
    }

    // Reverse result in-place
    for l, r := 0, len(result)-1; l < r; l, r = l+1, r-1 {
        result[l], result[r] = result[r], result[l]
    }

    return result
}

The Go implementation mirrors the Python logic. The key differences are explicit slice handling, append to add digits, and manual reversal of the slice since Go lacks a built-in reverse method. Integer division and modulo operations handle the carry and digit extraction similarly.

Worked Examples

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

i	num[i]	k	total	digit appended	k after division
3	0	34	34	4	3
2	0	3	3	3	0
1	2	0	2	2	0
0	1	0	1	1	0

result before reverse: [4,3,2,1], after reverse: [1,2,3,4].

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

i	num[i]	k	total	digit appended	k after division
2	4	181	185	5	18
1	7	18	25	5	2
0	2	2	4	4	0

result before reverse: [5,5,4], after reverse: [4,5,5].

Example 3: num = [2,1,5], k = 806

i	num[i]	k	total	digit appended	k after division
2	5	806	811	1	81
1	1	81	82	2	8
0	2	8	10	0	1
-1	-	1	1	1	0

result before reverse: [1,0,2,1], after reverse: [1,0,2,1].

Complexity Analysis

Measure	Complexity	Explanation
Time	O(max(n, log k))	We iterate through all digits of `num` and all digits of `k`.
Space	O(max(n, log k))	We store each digit of the result in a new array.

The time complexity reflects the fact that we process every digit in num and each digit of k exactly once. Space complexity corresponds to the array used to store the resulting sum.

Test Cases

# Provided examples
assert Solution().addToArrayForm([1,2,0,0], 34) == [1,2,3,4]  # standard case
assert Solution().addToArrayForm([2,7,4], 181) == [4,5,5]    # carry propagation
assert Solution().addToArrayForm([2,1,5], 806) == [1,0,2,1]  # result longer than num

# Edge cases
assert Solution().addToArrayForm([0], 5) == [5]              # zero num
assert Solution().addToArrayForm([9,9,9], 1) == [1,0,0,0]    # all nines
assert Solution().addToArrayForm([1,0,0,0], 9999) == [1,0,9,9,9]  # large k
assert Solution().addToArrayForm([5], 5) == [1,0]            # single digit sum overflow

Test	Why
[1,2,0,0], 34	Standard addition with carry
[2,7,4], 181	Carry propagation across multiple digits
[2,1,5], 806	Result has more digits than num
[0], 5	num is zero
[9,9,9], 1	Overflow across all digits
[1