algoadvance

Leetcode 989. Add to Array

Problem Statement

Given a non-negative integer represented as a non-empty array of digits (num), and a non-negative integer k, return the array-form of the integer num + k.

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

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

Clarifying Questions

  1. What is the maximum length of the array num?
  2. Can k be a very large number, or is there a constraint on its size?
  3. Are there any leading zeros in the num array?
  4. Is the input always valid (e.g., num is a non-empty array and k is a non-negative number)?

Assuming the constraints based on typical LeetCode problems:

Strategy

  1. We will iterate through the array from the last digit to the first because addition starts from the least significant digit (rightmost).
  2. Add k to the number represented by num starting from the least significant digit.
  3. Manage carry-over if the sum of a position exceeds 9.
  4. If after processing all digits, there remains a carry, it needs to be added at the beginning of the resulting list.
  5. Convert the list back to array-form to return.

Code

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

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

Time Complexity

The time complexity of this solution is (O(\max(N, \log_{10}K))), where N is the length of the num array and \log_{10}K is the number of digits in k. This is because we process each digit of both num and k.

This solution ensures that the problem is handled efficiently and correctly even when num and k are large.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI