Add to Array-Form of Integer

EASY

Description

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 <= 10⁴
0 <= num[i] <= 9
num does not contain any leading zeros except for the zero itself.
1 <= k <= 10⁴

Approaches

Checkout 2 different approaches to solve Add to Array-Form of Integer. Click on different approaches to view the approach and algorithm in detail.

Schoolbook Addition

This approach simulates the manual, pencil-and-paper method of adding two numbers. It processes the numbers from right to left (least significant digit to most significant), keeping track of a carry value at each step.

Algorithm

Initialize an empty LinkedList for the result.
Initialize a pointer i to the last index of num.
Loop as long as i is valid (>= 0) or k > 0.
Inside the loop, if i is valid, add num[i] to k.
Add the last digit of the current sum (k % 10) to the front of the result list.
Update k to be the carry (k / 10).
Decrement i.
Return the result list.

This is the most efficient way to solve the problem as it performs the addition in a single pass without any expensive type conversions or large object allocations. The algorithm iterates through the num array from right to left, adding the digits of k and any carry from the previous step. The integer k itself is used to carry over the sum to the next higher-order digit.

Algorithm Steps:

Initialize a LinkedList to store the result digits. A LinkedList is chosen for its efficient O(1) addFirst operation, which avoids a final reversal step.
Start a loop that continues as long as there are digits left in num to process or k (which holds the carry and remaining part of the number to be added) is greater than 0.
In each iteration, if there's a digit in num at the current position, add it to k.
The current digit for the result is k % 10.
The new carry is k / 10. We update k to this value for the next iteration.
Prepend the current digit (k % 10) to the result list.
Move to the next digit in num by decrementing the pointer.
After the loop, the LinkedList contains the digits of the sum in the correct order. Return it.

import java.util.LinkedList;
import java.util.List;

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        LinkedList<Integer> result = new LinkedList<>();
        int i = num.length - 1;

        while (i >= 0 || k > 0) {
            // Add the current digit of num if it exists
            if (i >= 0) {
                k += num[i];
                i--;
            }
            
            // The current digit of the sum is k % 10
            result.addFirst(k % 10);
            
            // The carry is k / 10
            k /= 10;
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(max(N, log10(k))), where N is the length of the `num` array. The loop runs once for each digit of the larger number. This is effectively O(N) given the constraints.Space Complexity: O(max(N, log10(k))) for the result list. If the output list is not considered auxiliary space, the space complexity is O(1).

Pros and Cons

Pros:

Highly efficient with optimal time and space complexity.
Avoids intermediate data structures like strings or BigInteger objects, reducing overhead.
Demonstrates a fundamental understanding of arithmetic operations.

Cons:

Slightly more complex to implement correctly compared to the BigInteger approach.

Code Solutions

Checking out 3 solutions in different languages for Add to Array-Form of Integer. Click on different languages to view the code.

class Solution {
public
  List<Integer> addToArrayForm(int[] num, int k) {
    int i = num.length - 1, carry = 0;
    LinkedList<Integer> ans = new LinkedList<>();
    while (i >= 0 || k > 0 || carry > 0) {
      carry += (i < 0 ? 0 : num[i--]) + k % 10;
      ans.addFirst(carry % 10);
      carry /= 10;
      k /= 10;
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Add to Array-Form of Integer

Patterns:

Math

Data Structures:

Array

Companies:

Avito |ByteDance |Zoho |