Code Implementation

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

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& num, int k) {
        vector<int> res;
        int i = num.size() - 1;
        while (i >= 0 || k > 0) {
            if (i >= 0) {
                k += num[i];
                i--;
            }
            res.push_back(k % 10);
            k /= 10;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};
      

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        LinkedList<Integer> res = new LinkedList<>();
        int i = num.length - 1;
        while (i >= 0 || k > 0) {
            if (i >= 0) {
                k += num[i];
                i--;
            }
            res.addFirst(k % 10);
            k /= 10;
        }
        return res;
    }
}
      

var addToArrayForm = function(num, k) {
    let res = [];
    let i = num.length - 1;
    while (i >= 0 || k > 0) {
        if (i >= 0) {
            k += num[i];
            i--;
        }
        res.push(k % 10);
        k = Math.floor(k / 10);
    }
    res.reverse();
    return res;
};
      

Problem Description

You are given an integer represented as an array num, where each element is a digit of the integer in left-to-right order (most significant digit first). You are also given an integer k. Your task is to add k to the integer represented by num and return the sum as an array of digits, also in left-to-right order.

• Each element in num is a digit (0-9).
• There is always one valid solution.
• You do not need to handle negative numbers or reuse elements.
• For example, if num = [1,2,0,0] and k = 34, the output should be [1,2,3,4] because 1200 + 34 = 1234.

Thought Process

The problem asks us to add a number to another number that is stored as an array of digits. At first, it might seem like we need to convert the array to an integer, add k, and then convert it back to an array. However, this approach can fail for very large numbers that do not fit in standard integer types.

Instead, we can mimic the process of addition as we do by hand: start from the least significant digit (the end of the array), add k digit by digit, and handle carry over to the next digit. This way, we never need to convert the whole array to a number, and we can handle numbers of any length.

The main idea is to process both num and k from the least significant digit, adding them together and managing the carry, until both are fully processed.

Solution Approach

• Step 1: Initialize an empty result array to store the answer digits.
• Step 2: Set a pointer i to the last index of num (rightmost digit).
• Step 3: Loop while either i is valid (i.e., there are digits left in num) or k is greater than 0.
  • If i is valid, add num[i] to k and decrement i.
  • Append k % 10 (the current least significant digit) to the result array.
  • Update k to k // 10 (remove the least significant digit, handling carry).
• Step 4: After the loop, the result array contains the answer digits in reverse order. Reverse it to get the correct order.
• Step 5: Return the result array.

This approach avoids converting the entire array to an integer, works for very large numbers, and efficiently handles all edge cases.

Example Walkthrough

Let's consider num = [2, 7, 4] and k = 181.

1. Start from the end: i = 2, num[2] = 4, k = 181
2. Add num[2] + k = 4 + 181 = 185
3. Append 185 % 10 = 5 to result, update k = 185 // 10 = 18, i = 1
4. Add num[1] + k = 7 + 18 = 25
5. Append 25 % 10 = 5 to result, update k = 25 // 10 = 2, i = 0
6. Add num[0] + k = 2 + 2 = 4
7. Append 4 % 10 = 4 to result, update k = 4 // 10 = 0, i = -1
8. Both i and k are done. Result is [5, 5, 4] (reversed).
9. Reverse to get [4, 5, 5], which is the correct answer (274 + 181 = 455).

Time and Space Complexity

• Brute-force approach: Converting the array to an integer, adding k, and converting back has time complexity O(N) but can fail for very large numbers due to integer overflow.
• Optimized approach (our solution):
  • Time Complexity: O(max(N, log K)), where N is the length of num and log K is the number of digits in k. We process each digit of both numbers once.
  • Space Complexity: O(max(N, log K)), since the result array can be at most one digit longer than the longer of num or k.

Summary

The "Add to Array-Form of Integer" problem is elegantly solved by simulating manual addition from the least significant digit, handling carry, and avoiding integer overflow. This approach is efficient, easy to implement, and works for very large numbers represented as arrays. By focusing on digit-by-digit processing, we avoid unnecessary conversions and ensure robust performance on all inputs.