Problem Description

You are given an integer represented as an array of its digits (called the "array-form"), where each element in the array is a single digit. The digits are ordered from left to right, with the leftmost digit being the most significant.

For example, if you have the number 1321, its array-form would be [1, 3, 2, 1].

Your task is to add an integer k to this array-form number and return the result also in array-form.

Input:

• num: An array of integers where each element is a digit (0-9) representing a number in array-form
• k: An integer to be added to the number represented by num

Output:

• Return an array representing the sum num + k in array-form

Example: If num = [1, 3, 2, 1] (representing 1321) and k = 34, the output should be [1, 3, 5, 5] (representing 1355, since 1321 + 34 = 1355).

The solution simulates the addition process digit by digit from right to left, handling carries along the way. It starts from the last digit of the array and adds k to it. The remainder when divided by 10 becomes the current digit, and the quotient becomes the new value of k (acting as the carry). This continues until both the array is fully processed and k becomes 0. The result is built in reverse order and then reversed at the end to get the correct array-form representation.

Intuition

Think about how we normally add two numbers by hand. We start from the rightmost digit (the ones place) and work our way left, carrying over any value greater than 9 to the next position. This is exactly what we need to do here.

The clever insight is that instead of converting the entire array to an integer, adding k, and then converting back to an array (which could cause overflow for very large numbers), we can treat k itself as our running carry value.

Consider adding 34 to 1321:

  1 3 2 1
+     3 4
---------
  1 3 5 5

Starting from the rightmost digit: we add 1 + 34 = 35. We keep 5 as the current digit and carry 3 (which is 35 divided by 10). Then we add 2 + 3 = 5, with no carry. This continues until we've processed all digits.

The key realization is that at each step, we can:

1. Add the current digit (if it exists) to k
2. Extract the rightmost digit of this sum using k % 10 - this becomes our current result digit
3. Update k to k // 10 - this becomes our carry for the next position

By treating k as both the number to add AND the carry, we elegantly handle all cases:

• When k is initially large (like 999), it naturally propagates through multiple positions
• When the array is exhausted but k still has value, we continue adding digits
• When both are exhausted (k = 0 and no more array digits), we're done

Building the result in reverse order (appending to the end) and then reversing at the end is more efficient than inserting at the beginning each time.

Learn more about Math patterns.

Solution Approach

The implementation follows the simulation approach, processing digits from right to left while maintaining a carry value.

Algorithm Steps:

1. Initialize variables:

   • Create an empty list ans to store the result digits
   • Set pointer i to the last index of the array (len(num) - 1)

2. Main loop: Continue while either we have digits to process (i >= 0) or there's still a carry value (k > 0):

   a. Add current digit to k:

   k += 0 if i < 0 else num[i]

   • If we're still within the array bounds, add the current digit to k
   • If we've exhausted the array, add 0 (effectively just processing the remaining carry)

   b. Extract digit and carry:

   k, x = divmod(k, 10)

   • Use divmod(k, 10) to simultaneously get:
     • x: The remainder (current digit to add to result)
     • k: The quotient (carry for the next position)

   c. Store the digit:

   ans.append(x)

   • Append the current digit to the result list

   d. Move to next position:

   i -= 1

   • Decrement the pointer to process the next digit from right to left

3. Reverse the result:

   return ans[::-1]

   • Since we built the answer from least significant to most significant digit, reverse it to get the correct order

Example Walkthrough:

For num = [1, 2, 0, 0] and k = 34:

• Round 1: i=3, k=34+0=34, divmod(34,10)=(3,4), append 4, k=3
• Round 2: i=2, k=3+0=3, divmod(3,10)=(0,3), append 3, k=0
• Round 3: i=1, k=0+2=2, divmod(2,10)=(0,2), append 2, k=0
• Round 4: i=0, k=0+1=1, divmod(1,10)=(0,1), append 1, k=0
• Result: [4,3,2,1] reversed gives [1,2,3,4] (representing 1234)

The time complexity is O(max(n, log k)) where n is the length of the array, and space complexity is O(max(n, log k)) for the result array.

Example Walkthrough

Let's walk through adding k = 56 to num = [2, 7] (representing 27).

Initial Setup:

• num = [2, 7], k = 56
• ans = [] (empty result list)
• i = 1 (pointing to the last index)

Iteration 1:

• Current digit: num[1] = 7
• Add to k: k = 56 + 7 = 63
• Extract digit and carry: 63 ÷ 10 = 6 remainder 3
  • New digit: 3
  • New k (carry): 6
• Append 3 to ans: ans = [3]
• Move pointer: i = 0

Iteration 2:

• Current digit: num[0] = 2
• Add to k: k = 6 + 2 = 8
• Extract digit and carry: 8 ÷ 10 = 0 remainder 8
  • New digit: 8
  • New k (carry): 0
• Append 8 to ans: ans = [3, 8]
• Move pointer: i = -1

Iteration 3:

• Check conditions: i = -1 (no more digits) and k = 0 (no carry)
• Exit loop

Final Step:

• Reverse the result: [3, 8] becomes [8, 3]
• Return [8, 3] (representing 83)

Verification: 27 + 56 = 83 ✓

This example demonstrates how the algorithm handles digit-by-digit addition with carry propagation, building the result in reverse order for efficiency.

Solution Implementation

Time and Space Complexity

Time Complexity: O(max(n, log k)), where n is the length of the array num and log k represents the number of digits in k.

The while loop continues as long as either i >= 0 (iterating through the array) or k > 0 (processing remaining digits of k). In each iteration:

• We traverse the array from right to left, which takes O(n) iterations
• If k has more digits than the array length, we continue processing until k becomes 0, which takes O(log k) additional iterations
• Each operation inside the loop (addition, division, modulo, append) takes O(1) time

Therefore, the total time complexity is O(max(n, log k)). When k is relatively small compared to the array size, this simplifies to O(n) as stated in the reference answer.

Space Complexity: O(1) (excluding the output array)

The algorithm uses only a constant amount of extra space:

• Variable i for indexing: O(1)
• Variable x for storing the digit: O(1)
• Variable k is modified in place: O(1)

The ans array stores the result, but since it's the required output, it's not counted in the space complexity analysis. Therefore, the auxiliary space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle Remaining Carry

A common mistake is only processing while there are digits in the array, forgetting that k might still have value after all digits are processed.

Incorrect approach:

while index >= 0:  # Wrong! Stops too early
    k += num[index]
    carry, digit = divmod(k, 10)
    result.append(digit)
    k = carry
    index -= 1

Issue: If num = [9, 9] and k = 1, this would give [0, 0] instead of [1, 0, 0] because it doesn't process the final carry.

Solution: Always check both conditions: while index >= 0 or k > 0

2. Building Result in Wrong Order Without Reversing

Another pitfall is appending digits in the wrong order or forgetting to reverse at the end.

Incorrect approach:

result = []
for i in range(len(num)):  # Processing left to right
    # ... addition logic
    result.append(digit)
return result  # Forgot to handle proper ordering

Solution: Either:

• Build from right to left and reverse at the end (as in the correct solution)
• Or use result.insert(0, digit) to prepend each digit (less efficient but clearer)

3. Modifying the Input Array In-Place

Some might try to modify the input array directly, which can cause issues when the result has more digits than the input.

Incorrect approach:

for i in range(len(num) - 1, -1, -1):
    num[i] += k
    k, num[i] = divmod(num[i], 10)
# What if k > 0 here? Can't extend num properly

Issue: When num = [9] and k = 99, the result should be [1, 0, 8], but you can't easily extend the input array.

Solution: Always create a new result array to handle size changes gracefully.

4. Integer Overflow in Other Languages

While Python handles arbitrary precision integers, in languages like Java or C++, converting the entire array to an integer could cause overflow.

Incorrect approach (in concept):

# This works in Python but would fail in other languages for large arrays
number = int(''.join(map(str, num)))
result_num = number + k
return [int(d) for d in str(result_num)]

Solution: Stick to the digit-by-digit simulation approach which works regardless of the number size.