Add to Array-Form of Integer

LeetCode 989: Add to Array-Form of Integer Solution & Explanation

Problem Overview

TL;DR: Treat the integer k as an initial carry value, iterate through the array from right to left, add the carry to the current digit, and propagate the new carry to the left.

The problem requires adding an integer k to a non-negative integer represented by an array of digits, num. The result must be returned as an array of digits. This is a variation of the classic "schoolbook addition" algorithm, where we align numbers by their least significant digit and manage carry-over operations.

This is a popular interview question found in LeetCode 989: Add to Array-Form of Integer. It tests your ability to manipulate arrays and handle edge cases related to number overflow and dynamic array sizing.

Brute Force Approach for Add to Array-Form of Integer

A naive approach would be to convert the array num into a standard integer type, add k to it, and then convert the resulting sum back into an array.

Pseudo-code:

function addToArrayForm(num, k):
    integer_value = 0
    for digit in num:
        integer_value = integer_value * 10 + digit
    
    total_sum = integer_value + k
    
    return convert_to_array(total_sum)

Why this fails: While mathematically sound, this approach fails due to integer overflow. The constraint 1 <= num.length <= 10^4 means num can have up to 10,000 digits. Standard integer types (like long long in C++ or long in Java) can only store up to approximately 19 digits. Attempting to convert num to a primitive integer will cause a runtime error or undefined behavior in strongly typed languages. Even in languages like Python that support arbitrary-precision integers, this approach ignores the algorithmic intent of array manipulation.

Algorithm Strategy: Array/Matrix Manipulation Patterns

1. Reverse Iteration: Traverse the array num starting from the last element (least significant digit) towards the first.
2. Accumulate and Update: At each step i, add the current value of k to num[i].
   • The new digit at this position is num[i] % 10.
   • The new carry to be propagated left is k = num[i] / 10.
   • Store the new digit in a result list (or modify num in place if allowed, though a separate result list is cleaner for handling size expansion).
3. Remaining Carry: After the loop finishes, if k > 0, it means the carry has extended beyond the original size of num. While k > 0, extract the last digit (k % 10), add it to the result, and divide k by 10.
4. Finalize: Since we built the result from least significant to most significant, reverse the result list to obtain the correct order.

Execution Flow

Let's trace num = [2, 1, 5], k = 806.

1. Initialization: i points to index 2 (value 5). Result list is empty.
2. Iteration 1 (i=2):
   • Current digit num[2] is 5.
   • Add k: 5 + 806 = 811.
   • New digit: 811 % 10 = 1. Add 1 to result. Result: [1].
   • Update k: 811 / 10 = 81.
   • Decrement i to 1.
3. Iteration 2 (i=1):
   • Current digit num[1] is 1.
   • Add k: 1 + 81 = 82.
   • New digit: 82 % 10 = 2. Add 2 to result. Result: [1, 2].
   • Update k: 82 / 10 = 8.
   • Decrement i to 0.
4. Iteration 3 (i=0):
   • Current digit num[0] is 2.
   • Add k: 2 + 8 = 10.
   • New digit: 10 % 10 = 0. Add 0 to result. Result: [1, 2, 0].
   • Update k: 10 / 10 = 1.
   • Decrement i to -1.
5. Remaining Carry:
   • Loop ends because i < 0.
   • Check k: k is 1 (greater than 0).
   • Add k % 10 (1) to result. Result: [1, 2, 0, 1].
   • Update k: 1 / 10 = 0.
6. Reverse:
   • Reverse [1, 2, 0, 1] to get [1, 0, 2, 1].

Proof of Correctness

The algorithm is correct because it simulates positional notation addition.

• Base Case: The least significant digit is calculated as (d + k) % 10, correctly capturing the unit place.
• Inductive Step: The integer division (d + k) / 10 correctly shifts the magnitude of the excess value to the next power of 10. By adding this quotient to the next digit to the left, we maintain the invariant that k always holds the value carried over from the previous lower-order positions.
• Termination: The process continues until all array digits are processed and the carry k is reduced to 0, ensuring no value is lost.

Pattern Reuse Notes

The "Array - Plus One (Handling Carry)" pattern is fundamental for arbitrary-precision arithmetic.

• LeetCode 66: Plus One: A simplified version where k is always 1. The carry logic is identical.
• LeetCode 43: Multiply Strings: Uses this addition logic as a subroutine. After multiplying digits, the results are added together using the same carry propagation strategy.
• LeetCode 67: Add Binary: Applies the same pattern but in base-2 instead of base-10. The modulo and division operations change to % 2 and / 2, but the structure remains the same.

Reference Implementation

C++ Solution for LeetCode 989

1class Solution {
2public:
3    vector<int> addToArrayForm(vector<int>& num, int k) {
4        vector<int> result;
5        int n = num.size();
6        int i = n - 1;
7
8        // Iterate while there are digits in num or carry k remains
9        while (i >= 0 || k > 0) {
10            // Add num[i] to k if i is valid
11            if (i >= 0) {
12                k += num[i];
13                i--;
14            }
15            
16            // The current digit is k % 10
17            result.push_back(k % 10);
18            
19            // The carry for the next position is k / 10
20            k /= 10;
21        }
22
23        // The result was built backwards, so reverse it
24        reverse(result.begin(), result.end());
25        return result;
26    }
27};

Java Solution for LeetCode 989

1import java.util.ArrayList;
2import java.util.Collections;
3import java.util.List;
4
5class Solution {
6    public List<Integer> addToArrayForm(int[] num, int k) {
7        List<Integer> result = new ArrayList<>();
8        int i = num.length - 1;
9
10        // Iterate while there are digits in num or carry k remains
11        while (i >= 0 || k > 0) {
12            if (i >= 0) {
13                k += num[i];
14                i--;
15            }
16            
17            // Add the last digit of the current sum to the list
18            result.add(k % 10);
19            
20            // Carry over the rest
21            k /= 10;
22        }
23
24        // Reverse to get the correct order
25        Collections.reverse(result);
26        return result;
27    }
28}

Python Solution for LeetCode 989

1class Solution:
2    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
3        result = []
4        i = len(num) - 1
5        
6        # Iterate while there are digits in num or carry k remains
7        while i >= 0 or k > 0:
8            if i >= 0:
9                k += num[i]
10                i -= 1
11            
12            # Append the last digit of k to result
13            result.append(k % 10)
14            
15            # Update k to be the carry
16            k //= 10
17            
18        # Reverse list to get correct order
19        return result[::-1]