989. Add to Array-Form of Integer - Explanation

Problem Link

1. Reverse and Add

Intuition

Adding two numbers digit by digit is straightforward when we start from the least significant digit. Since the array represents a number with the most significant digit first, we can either reverse the array or process it from the end.

The trick here is to treat k as a running sum that absorbs both the addition and the carry. At each step, we add the current digit to k, extract the last digit of k as our result digit, and divide k by 10 to prepare for the next iteration. This elegantly combines the carry propagation into a single variable.

Algorithm

1. Process the array from right to left (or reverse it first).
2. For each position i:
   • Add num[i] to k.
   • The result digit at this position is k % 10.
   • Update k = k / 10 to carry over any excess.
3. After processing all digits, if k > 0, continue extracting digits from k.
4. Reverse the result (if built in reverse order) and return.

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

Time & Space Complexity

• Time complexity: $O(max(n, m))$
• Space complexity: $O(n)$.

Where $n$ is the size of the array $num$ and $m$ is the number of digits in $k$.

---

2. Without Reverse()

Intuition

We can avoid the explicit reverse operation by inserting digits at the front of our result as we compute them. Using a deque (double-ended queue) or linked list allows O(1) insertion at the front.

The logic remains the same: process from right to left, compute each digit with the carry, and build the result. The difference is just in how we construct the output to avoid a final reversal step.

Algorithm

1. Initialize a deque or linked list for the result, and set carry = 0.
2. Start from the last index of num and the last digit of k.
3. While there are digits remaining in num, digits remaining in k, or carry > 0:
   • Compute sum = carry + num[i] (if valid) + k % 10.
   • Insert sum % 10 at the front of the result.
   • Update carry = sum / 10.
   • Move to the next digit: decrement i and divide k by 10.
4. Return the result as a list.

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        from collections import deque
        result = deque()
        i = len(num) - 1
        carry = 0

        while i >= 0 or k > 0 or carry > 0:
            digit = k % 10
            sum_val = carry + (num[i] if i >= 0 else 0) + digit

            result.appendleft(sum_val % 10)
            carry = sum_val // 10

            k //= 10
            i -= 1

        return list(result)

Time & Space Complexity

• Time complexity: $O(max(n, m))$
• Space complexity: $O(n)$

Where $n$ is the size of the array $num$ and $m$ is the number of digits in $k$.

---

Common Pitfalls

Forgetting the Final Carry

After processing all digits of the array and k, there may still be a remaining carry. Forgetting to handle this results in incorrect answers for cases like [9,9,9] + 1 = [1,0,0,0].

# Wrong: stopping when array and k are exhausted
while i >= 0 or k > 0:  # Missing: or carry > 0
    # ...

Processing Digits in Wrong Order

The array stores the most significant digit first, but addition needs to start from the least significant digit. Forgetting to process from right to left (or reverse the array) produces wrong results.

# Wrong: processing from left to right
for i in range(len(num)):  # Should be range(len(num)-1, -1, -1)
    k += num[i]