#989

Easy

LeetCode Problem Workspace

Add to Array-Form of Integer

Compute the sum of an integer and a number represented as an array, efficiently handling digit carries and array traversal.

array math

Problem Statement

You are given an array num representing the digits of a non-negative integer from most significant to least significant. Your task is to add an integer k to this number and return the resulting sum in array-form, preserving digit order and handling carries properly.

For example, if num = [1,2,0,0] and k = 34, the result is [1,2,3,4] because 1200 + 34 = 1234. Handle all additions digit by digit, ensuring correctness for inputs where num can be up to length 10^4 and k can be up to 10^4.

Examples

Example 1

Input: num = [1,2,0,0], k = 34

Output: [1,2,3,4]

1200 + 34 = 1234

Example 2

Input: num = [2,7,4], k = 181

Output: [4,5,5]

274 + 181 = 455

Example 3

Input: num = [2,1,5], k = 806

Output: [1,0,2,1]

215 + 806 = 1021

Constraints

1 <= num.length <= 104
0 <= num[i] <= 9
num does not contain any leading zeros except for the zero itself.
1 <= k <= 104

Solution Approach

Iterate from the End of the Array

Start from the least significant digit of num and add k's last digit. Track carry by using modulo 10 and integer division for the next iteration. Append each result to a temporary list and reverse at the end to get correct order.

Update k Dynamically

At each step, divide k by 10 to move to the next digit. This ensures that the addition aligns correctly with num's digits and reduces k progressively, allowing proper handling when num is shorter or longer than the number of digits in k.

Handle Remaining Carry and Extra Digits

After traversing num, continue processing any remaining digits of k and carry. Prepend or append remaining digits as needed to ensure the final array correctly represents the total sum without losing any significant digit.

Complexity Analysis

Metric	Value
Time	O(\max(N, \log K))
Space	O(\max(N, \log K))

Time complexity is O(max(N, log K)) because each digit of num and each digit of k is processed once. Space complexity is O(max(N, log K)) due to storing the result array and any intermediate digits.

What Interviewers Usually Probe

Expect candidates to handle carry propagation correctly for varying array lengths.
Check if the solution avoids converting the array entirely into an integer to prevent overflow.
Look for understanding of digit-wise addition and array reversal to maintain correct order.

Common Pitfalls or Variants

Common pitfalls

Forgetting to reverse the result array at the end leading to incorrect digit order.
Not handling remaining carry after finishing array traversal, which can produce missing leading digits.
Assuming k fits into integer conversion, which fails for large num arrays, violating constraints.

Follow-up variants

Adding two array-form integers instead of an integer k, increasing the need for synchronized digit iteration.
Subtracting an integer from array-form integer, testing handling of borrow instead of carry.
Supporting negative k, requiring careful treatment of sign and potential negative results in array form.

FAQ

What is the main pattern in Add to Array-Form of Integer?

The primary pattern is array plus math, handling each digit with carry propagation instead of converting the entire array to an integer.

Can num contain leading zeros?

No, num does not contain leading zeros except when it is the zero itself.

How do I handle cases where k has more digits than num?

Continue adding k's digits and carry after num is fully processed, appending new digits to the result as needed.

What is the time complexity for this problem?

The time complexity is O(max(N, log K)) since each digit of num and each digit of k is processed once.

Can GhostInterview help with Add to Array-Form of Integer?

Yes, GhostInterview assists by computing digit sums, managing carry, and producing the correct array-form efficiently.

terminal

Solution

Solution 1: Simulation

We can start from the last digit of the array and add each digit of the array to $k$. Then, divide $k$ by $10$, and use the remainder as the current digit's value, with the quotient as the carry. Continue this process until the array is fully traversed and $k = 0$. Finally, reverse the answer array.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        ans = []
        i = len(num) - 1
        while i >= 0 or k:
            k += 0 if i < 0 else num[i]
            k, x = divmod(k, 10)
            ans.append(x)
            i -= 1
        return ans[::-1]

Continue Practicing

#996 number of squareful arrays #976 largest perimeter triangle #973 k closest points to origin