Scale Engineer

Add to Array-Form of Integer

Easy
#0943Time: 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: O(max(N, log10(k))) for the result list. If the output list is not considered auxiliary space, the space complexity is O(1).3 companies
Patterns
Math
Data structures
Array
Companies
AvitoByteDanceZoho

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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:

  1. 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.
  2. 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.
  3. In each iteration, if there's a digit in num at the current position, add it to k.
  4. The current digit for the result is k % 10.
  5. The new carry is k / 10. We update k to this value for the next iteration.
  6. Prepend the current digit (k % 10) to the result list.
  7. Move to the next digit in num by decrementing the pointer.
  8. 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

Time

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

O(max(N, log10(k))) for the result list. If the output list is not considered auxiliary space, the space complexity is O(1).

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem