{x}
blog image

Add to Array-Form of Integer

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.

 

Example 1:

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

Example 2:

Input: num = [2,7,4], k = 181
Output: [4,5,5]
Explanation: 274 + 181 = 455

Example 3:

Input: num = [2,1,5], k = 806
Output: [1,0,2,1]
Explanation: 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 Explanation for LeetCode 989: Add to Array-Form of Integer

This problem asks to add an integer k to the array-form representation of another integer num and return the result as an array-form integer. The solution involves simulating addition as we would do manually, handling carry-overs.

Approach

The core idea is to iterate through the digits of num (from right to left) and add the corresponding digits of k. We maintain a carry variable to track any carry-over from previous additions. The process continues until all digits of num and k are processed and the carry is zero.

Detailed Explanation with Code (Python3)

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        i, carry = len(num) - 1, 0
        ans = []
        while i >= 0 or k or carry:  # Continue until all digits and carry are processed
            carry += (0 if i < 0 else num[i]) + (k % 10) # Add current digit from num (or 0 if none left), and the last digit of k
            carry, v = divmod(carry, 10)  # Separate carry and the last digit of the sum
            ans.append(v) # append the last digit to the answer
            k //= 10  # Remove the last digit from k
            i -= 1  # Move to the next digit in num
        return ans[::-1]  # Reverse the answer to get the correct order

Line-by-line explanation:

  1. i, carry = len(num) - 1, 0: Initialize i to point to the last digit of num and carry to 0.
  2. while i >= 0 or k or carry:: This loop continues as long as there are digits in num or k remaining or there's a carry.
  3. carry += (0 if i < 0 else num[i]) + (k % 10): Add the current digit from num (or 0 if i is negative, meaning we've processed all digits of num) and the last digit of k to the carry.
  4. carry, v = divmod(carry, 10): Use divmod to get both the quotient (new carry) and the remainder (last digit v) after dividing by 10.
  5. ans.append(v): Add the last digit v to the ans list.
  6. k //= 10: Integer division to remove the last digit from k.
  7. i -= 1: Decrement i to move to the next digit in num.
  8. return ans[::-1]: Reverse the ans list because we added digits from right to left.

Time and Space Complexity

  • Time Complexity: O(max(N, M)), where N is the length of num and M is the number of digits in k. This is because the while loop iterates at most N+M times.
  • Space Complexity: O(max(N, M)), as the ans list could potentially store up to N+M digits. In the worst case, where all additions result in a carry, the result could have one more digit than the input.

This solution efficiently handles the addition without explicitly converting the array to an integer, avoiding potential integer overflow issues for very large numbers. The use of divmod makes the code clean and concise. The solutions in other languages follow a very similar logic.