Add to Array-Form of Integer: Digit-by-Digit Addition with Carry
LeetCode 989, Add to Array-Form of Integer, asks you to add an integer k to a number that is already represented as an array of its digits. You return the sum in the same array-of-digits format.
The problem
You are given a non-negative integer represented as an array num where num[i] is the i-th digit of the number from left to right. You are also given an integer k. Return the array-form of num + k.
For example, if num = [1, 2, 0, 0] and k = 34, the number is 1200 and you need to return [1, 2, 3, 4] because 1200 + 34 = 1234.
The brute force approach
You might be tempted to convert the digit array into a single integer, add k, then convert back to an array. In Python this actually works because integers have arbitrary precision. But in most languages, the number can have up to 10,000 digits, which overflows any standard integer type. Even in Python, converting a 10,000-digit array to an integer and back is wasteful when a simpler approach exists.
The key insight
Treat k itself as the carry. Start from the rightmost digit of num, add k to it, write sum % 10 as the new digit, and set k = sum / 10 (integer division) for the next iteration. This is exactly how you would do long addition by hand: process one column at a time from right to left, carrying any overflow.
Instead of extracting digits from k separately, just add the entire k to the current digit. The modulo operation gives you the digit to write, and the integer division gives you the carry for the next column. This eliminates the need to track a separate carry variable.
Step-by-step walkthrough
Step 1: Rightmost digit (index 3)
num[3] = 0, k = 34. Take 34 % 10 = 4. Sum = 0 + 4 = 4. Write 4, carry = 0. k becomes 34 / 10 = 3.
Step 2: Second digit (index 2)
num[2] = 0, k = 3. Take 3 % 10 = 3. Sum = 0 + 3 = 3. Write 3, carry = 0. k becomes 0.
Step 3: Third digit (index 1)
num[1] = 2, k = 0. Sum = 2 + 0 = 2. Write 2, carry = 0. No more k digits to process.
Step 4: Leftmost digit (index 0)
num[0] = 1, k = 0. Sum = 1 + 0 = 1. Write 1, carry = 0. All digits processed. Result: [1, 2, 3, 4].
The code
def addToArrayForm(num, k):
i = len(num) - 1
while i >= 0 or k > 0:
if i >= 0:
k += num[i]
num[i] = k % 10
else:
num.insert(0, k % 10)
k //= 10
i -= 1
return num
The loop walks from right to left through the array. At each position, it adds k to the current digit. The result modulo 10 becomes the new digit at that position, and k is updated to the carry (the result of integer division by 10).
If k still has remaining value after processing all digits of num, the loop continues. Each remaining carry digit is inserted at the front of the array. This handles cases where the sum has more digits than the original number, like [9, 9] + 1 = [1, 0, 0].
Using k as both the addend and the carry variable is the elegant trick here. You never need a separate carry variable because k naturally absorbs that role after each iteration.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Convert to integer and back | O(n) where n = number of digits | O(n) |
| Digit-by-digit addition | O(max(n, log k)) | O(1) extra (in-place modification) |
The digit-by-digit approach processes each digit exactly once. If k has more digits than num, the extra iterations handle the overflow. The space is O(1) extra beyond the input array itself, though in the worst case the result array grows by one element (for example, [9, 9, 9] + 1 = [1, 0, 0, 0]).
The building blocks
Right-to-left digit processing
This pattern of iterating from the least significant digit to the most significant digit appears in every addition, multiplication, and carry-propagation problem. You always start at the rightmost position because that is where the carry originates. Mastering this traversal direction makes problems like Add Binary, Plus One, and Multiply Strings feel like variations of the same theme.
Carry as a running accumulator
Rather than maintaining a separate boolean or integer carry, this solution folds the carry into k itself. After processing each digit, k holds whatever needs to be added to the next column. This same idea works in Add Two Numbers (linked lists) and Add Binary (strings), where you keep a running sum that propagates leftward.
Edge cases
k is larger than num. If num = [0] and k = 1000, the loop extends beyond the array. After processing index 0, it keeps inserting digits until k is fully consumed, producing [1, 0, 0, 0].
Carry propagation across all digits. When num = [9, 9, 9] and k = 1, every digit generates a carry. The result is [1, 0, 0, 0], one digit longer than the input.
k is zero. The loop processes each digit of num but adds nothing. The array is returned unchanged.
Single-digit array. num = [5] and k = 7 gives a sum of 12, which produces [1, 2]. The array grows from length 1 to length 2.
From understanding to recall
The core loop here is short, but the details matter. Do you add k to num[i] or k % 10 to num[i]? (You add all of k, and let modulo sort it out.) Do you use k //= 10 or k -= num[i]? (Integer division by 10, because k absorbed the full sum.)
These small decisions are exactly the kind that slip under pressure. Spaced repetition locks them in. You practice the right-to-left loop once today, again in two days, again in a week. By the third repetition, the pattern of "add k, write mod 10, divide k by 10" is automatic. You are not rederiving it. You are recalling it.
This problem is also a perfect warmup before tackling harder digit-manipulation problems like Multiply Strings or Add Two Numbers II.
Related posts
- Add Binary - Same digit-by-digit addition concept applied to binary strings
- Plus One - A simpler version where you only add 1 to a digit array
- Add Two Numbers - Addition via linked lists using the same carry technique