Add to Array-Form of Integer

Difficulty: Easy | Acceptance: 45.50% | Paid: No Topics: Array, Math

The array-form of an integer num is an array representing its digits in left-to-right order.

• For example, for num = 1321, the array form is [1,3,2,1].

Given num, the array-form of an integer, and an integer k, return the array-form of the integer num + k.

• Examples
• Constraints
• Elementary Addition (Iterative with Carry)
• Reverse and Add

Examples

Example 1:

Input: num = [1,2,0,0], k = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

Example 2:

Input: num = [2,1,5], k = 806
Output: [1,0,2,1]
Explanation: 215 + 806 = 1021

Example 3:

Input: num = [0], k = 10000
Output: [1,0,0,0,1]
Explanation: 0 + 10000 = 10000

Constraints

1 <= num.length <= 10^4
0 <= num[i] <= 9
num does not contain any leading zeros, except for the number 0 itself.
0 <= k <= 10^4

Elementary Addition (Iterative with Carry)

Intuition We can simulate the process of adding numbers digit by digit, starting from the least significant digit (the end of the array) to the most significant digit (the start). We maintain a carry value to handle sums greater than 9.

Steps

• Initialize an empty list res to store the result, i to the last index of num, and carry to 0.
• Loop while i >= 0 or k > 0 or carry > 0.
• In each iteration, take the current digit from num (if available) and the last digit of k (k % 10).
• Calculate the sum of the two digits and the carry.
• Update carry to sum / 10 and append sum % 10 to res.
• Decrement i and update k to k / 10.
• Finally, reverse res to get the correct order.

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

Complexity

• Time: O(max(N, log K)) where N is the length of num. We iterate through the digits of num and k.
• Space: O(max(N, log K)) to store the result.
• Notes: This is the most efficient approach as it avoids string conversions and handles large numbers naturally.

Reverse and Add

Intuition By reversing the array, we can process the least significant digits at index 0, simplifying the indexing logic. We add the digits of k to the reversed array, handle carries, and then reverse the result back.

Steps

• Reverse the input array num.
• Iterate through the array while k > 0, adding k % 10 to the current element.
• Handle carry by propagating it to the next element or pushing a new element if the end of the array is reached.
• If k still has digits after processing the array, push the remaining digits of k to the array.
• Reverse the array back to its original form.

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

Complexity

• Time: O(N + log K) for the reversals and the addition loop.
• Space: O(1) extra space if modifying in-place (excluding the space for the output list itself).
• Notes: Modifying the input in-place can be slightly more efficient in space but requires reversing the array twice.