Problem

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

Example 1:

1
2
3

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

Example 2:

1
2
3

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

Example 3:

1
2
3

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

Solution

Method 1 - Addition digit by digit

Here is the approach:

  1. Start from the least significant digit of num (the last element of the array) and add digits of k to it.
  2. Manage the carry during addition.
  3. If there are remaining digits in k after processing all digits of num, continue adding the carry to those digits.
  4. If there’s any remaining carry after processing both num and k, add those carry digits to the result.
  5. The final result should be reversed to get the correct order of the array-form.\

Here are the steps:

  1. Initialize variables to hold the carry and the result array.
  2. Traverse num and k from right to left, add corresponding digits, and manage the carry.
  3. If digits in k are exhausted before num, continue processing the remaining digits of num with the carry.
  4. If digits in num are exhausted before k, convert and process remaining digits of k.
  5. Add remaining carry if any.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer> result = new ArrayList<>();
        int carry = k;
        int n = num.length;

        for (int i = n - 1; i >= 0; i--) {
            carry += num[i];
            result.add(carry % 10);
            carry /= 10;
        }

        while (carry > 0) {
            result.add(carry % 10);
            carry /= 10;
        }

        Collections.reverse(result);
        return result;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def addToArrayForm(num, k):
    num = num[::-1]  # Reverse the digit array
    carry = k
    result = []

    for digit in num:
        carry += digit
        result.append(carry % 10)
        carry //= 10

    while carry > 0:
        result.append(carry % 10)
        carry //= 10

    return result[::-1]  # Reverse result to return in correct order

Complexity

  • Time: O(n + m), where n is the length of num and m is the number of digits in k.
  • Space: O(max(n, m)), The space required to store the result array.