989. Add to Array-Form of Integer

EasyArrayMath
Leetcode Link

Problem Description

The problem is to implement the addition of a non-negative integer k to a number represented as an array, where each element of the array represents a single digit of the number in the correct order. For instance, if num = 1321, then the array form would be [1,3,2,1]. If we were to add k = 9 to this number, we're trying to find the array form of 1321 + 9, which would result in [1,3,3,0].

This is akin to how we perform addition by hand, starting from the rightmost digit (the least significant digit) and adding it to the corresponding digit of the other number (if available), carrying over the excess to the next digit on the left if the sum exceeds 9.

Intuition

This solution approach leverages the simple idea of adding two numbers together just as we would on paper, digit by digit from right to left, handling carry as needed.

We initialize a pointer i to the last index of the num array and set carry to 0. In a loop, we perform the following until we have exhausted all digits in the num array and fully added k and accounted for any remaining carry:

  • We calculate the total sum for the current digit by adding the appropriate digit from num (or 0 if we've passed the beginning of num), the last digit of k, and any carry from the previous step.
  • We then use the divmod() function to both determine the digit to append to our answer in reverse (v) and the new carry value, ensuring that we only carry over when the sum is 10 or greater.
  • Append v to the answer array ans.
  • Update the value of k to reflect the leftover part after extracting the last digit by performing integer division by 10.
  • Decrement the index i to move to the next digit to the left.

Once the loop concludes (all digits and the carry have been processed), we reverse the ans array to represent the correct number as the digits have been appended in reverse order, starting with the least significant digit. This reversed ans array represents the num + k in array form, which is what we return as the solution.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following shows the order of node visit in a Breadth-first Search?

Solution Approach

The implementation of the solution is a straightforward simulation of the addition operation that we perform manually between numbers. Here is the step-by-step break down:

  1. Initialize the index i to point to the last digit of the input array num which represents the least significant digit of the number we are given. Also, initialize a carry variable to 0, which will keep track of any carryover during the addition process.

  2. Create an empty list ans that will store the result of the addition in reverse order.

  3. Execute a while loop with the condition to continue as long as there is a digit remaining in the num array (i >= 0), or there is still a part of k that hasn't been added (k), or there is a carry from the previous addition (carry).

  4. The sum for the current position is calculated by adding the current digit of num array, if any (num[i] or 0 if i is less than 0), the last digit of k (k % 10), and the current carry. This is done using the line:

    1carry += (0 if i < 0 else num[i]) + (k % 10)

  5. The carry and the value to append to the result list, v, are determined by using divmod():

    1carry, v = divmod(carry, 10)

    This operation returns the quotient that becomes the next carry and the remainder v which is the digit to be appended to the answer.

  6. Append v to the ans list:

    1ans.append(v)

  7. The next digit of k is obtained by reducing k by one decimal place using the floor division operation:

    1k //= 10

  8. Decrement the index i to move the pointer to the left, preparing for the next iteration to add the next higher order digit.

  9. After the loop exits, the answer list ans contains the digits of the result in reversed order since we started adding from the least significant digit. Therefore, we reverse ans to correct the order:

    1return ans[::-1]

  10. Return the reversed ans list as the final output, which now represents the num + k in the correct array-form.

In summary, the algorithm uses simple arithmetic and an iterative approach to simulate the addition process with careful bookkeeping of carries. The data structure used is a list to store the digits of the result which is eventually reversed to match the expected output format.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Example Walkthrough

Let's take a small example to illustrate the solution approach.

Suppose we have the array num = [2,5,6] which represents the number 256 and we want to add k = 34 to this number. We expect to find the array form of 256 + 34, which would result in [2,9,0].

Here is how the algorithm would process this example:

  1. Initialize the index i to 2 since the last digit of num is at index 2. Also, the carry variable is initialized to 0.

  2. An empty list ans is created to store the result.

  3. Enter the while loop which continues as long as i >= 0, k > 0, or carry is not 0.

  4. In the first iteration, i is 2, there is no carry, and k is 34. So, we calculate:

    1carry += num[2] + k % 10   # carry += 6 + 4

    carry now becomes 10. The next step is to split this into carry and v:

    1carry, v = divmod(10, 10)   # carry = 1, v = 0

    We append 0 to ans (since v = 0) and adjust k and i:

    1k //= 10   # k becomes 3
2i -= 1     # i becomes 1

  5. The next iteration starts with i = 1, carry = 1, and k = 3. The sum is:

    1carry += num[1] + k % 10   # carry += 5 + 3

    carry now becomes 9. Again, we split this into carry and v:

    1carry, v = divmod(9, 10)   # carry = 0, v = 9

    We append 9 to ans and adjust k and i:

    1k //= 10   # k becomes 0
2i -= 1     # i becomes 0

  6. The final iteration starts with i = 0, carry = 0, and k = 0. We perform the addition:

    1carry += num[0] + k % 10   # carry += 2 + 0

    carry now becomes 2. Split into carry and v:

    1carry, v = divmod(2, 10)   # carry = 0, v = 2

    We append 2 to ans:

    1ans.append(v)

  7. The loop finishes since i is now less than 0, k is 0, and carry is also 0. The result list ans is currently [0, 9, 2].

  8. We reverse ans to get the correct order:

    1ans[::-1]   # becomes [2, 9, 0]

  9. The final output is [2, 9, 0], which is the correct array representation of 256 + 34.

This walkthrough demonstrates each step of the algorithm on a small example, successfully showing how the solution approach adds two numbers when one is given as an array and the other as an integer (k).

Solution Implementation

1from typing import List
2
3class Solution:
4    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
5        current_index, carry_over = len(num) - 1, 0
6        result = []
7      
8        # Loop until we've processed each digit of `num` and `k`
9        # as well as any remaining carry over value.
10        while current_index >= 0 or k or carry_over:
11            # If the current index is valid, extract the digit from `num`, 
12            # otherwise use 0. Add the last digit of `k` and the carry over.
13            carry_over += (num[current_index] if current_index >= 0 else 0) + (k % 10)
14            # Use divmod to get the new carry over and the digit to be added to the result.
15            carry_over, digit = divmod(carry_over, 10)
16            result.append(digit)
17            # Update `k` and `current_index` for the next iteration.
18            k //= 10
19            current_index -= 1
20      
21        # The `result` list is currently in reverse, as digits were added from 
22        # the least significant digit (rightmost). We need to reverse it before returning.
23        return result[::-1]
24
1class Solution {
2    public List<Integer> addToArrayForm(int[] num, int k) {
3        int n = num.length - 1; // Initialize the index to the last element of the input array
4        int carry = 0; // To hold carry-over values during addition
5        LinkedList<Integer> result = new LinkedList<>(); // Using LinkedList to utilize addFirst method
6      
7        // Loop until we've processed all elements of num, or until k becomes 0, or until there's no carry left
8        while (n >= 0 || k > 0 || carry > 0) {
9            // If n is within bounds, add num[n] to carry; else add 0.
10            // Also add the last digit of k to carry
11            carry += (n < 0 ? 0 : num[n--]) + k % 10;
12          
13            // Add the unit's place of carry to the front of result
14            result.addFirst(carry % 10);
15          
16            // Remove the unit's place digit from carry and k
17            carry /= 10;
18            k /= 10;
19        }
20      
21        return result;
22    }
23}
24
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Adds an integer k to a large integer represented as a vector of digits.
7    vector<int> addToArrayForm(vector<int>& num, int k) {
8        int numIndex = num.size() - 1; // Start from the last digit of the number.
9        int carry = 0; // Initialize carry for addition.
10        vector<int> result; // The result vector to store the sum.
11
12        // Iterate until all digits are processed, or there is no carry, or k is not zero.
13        while (numIndex >= 0 || k > 0 || carry > 0) {
14            // If numIndex is within bounds, add the current digit to carry.
15            // Otherwise, add 0 (when numIndex < 0).
16            carry += (numIndex >= 0 ? num[numIndex] : 0) + (k % 10);
17            result.push_back(carry % 10); // Extract the last digit of carry and add it to result.
18            carry /= 10; // Update carry for the next iteration.
19            k /= 10; // Move to the next digit in k.
20            numIndex--; // Move to the previous digit in num.
21        }
22
23        // The result currently contains the digits in reverse order.
24        reverse(result.begin(), result.end()); // Reverse the result to get the correct order.
25      
26        return result;
27    }
28};
29
1function addToArrayForm(numArray: number[], k: number): number[] {
2    // Convert 'k' to an array of its digits
3    let kArray: number[] = [...String(k)].map(Number);
4  
5    // Initialize the answer array to hold the result
6    let answer: number[] = [];
7  
8    // Sum is used to handle the current value while adding digits
9    let carry: number = 0;
10  
11    // Process while there are digits in 'numArray' or 'kArray', or if there is a carry value
12    while (numArray.length || kArray.length || carry) {
13        // Pop the last digit from 'numArray' or use 0 if empty
14        let numDigit = numArray.pop() || 0;
15      
16        // Pop the last digit from 'kArray' or use 0 if empty
17        let kDigit = kArray.pop() || 0;
18      
19        // Add the digits and the carry
20        carry += numDigit + kDigit;
21      
22        // Unshift (insert at the beginning) the last digit of the sum into 'answer'
23        answer.unshift(carry % 10);
24      
25        // Floor division by 10 to get a new carry value
26        carry = Math.floor(carry / 10);
27    }
28  
29    // Return the result stored in 'answer'
30    return answer;
31}
32
Not Sure What to Study? Take the 2-min Quiz：

How does quick sort divide the problem into subproblems?

Time and Space Complexity

Time Complexity

The time complexity of the code is O(max(N, logK)) where N is the number of digits in num and logK represents the number of digits in k. This is because the while loop runs once for each digit of the number num and for each digit of the number k. When k has more digits than num, the loop will continue until all digits of k have been processed. In the reverse situation, it will process all the digits of num even if k is already reduced to zero.

Space Complexity

The space complexity of the code is O(max(N, logK)) because we create a list ans that stores the result, which in the worst case will have max(N, logK) digits (the maximum out of the number of digits in num and the number of digits in k after addition). Furthermore, space is used for variables i, carry, v, and the stack space for the recursive call when reversing the answer list, but these do not depend on the size of the inputs and thus contribute only a constant factor, which is negligible when analyzing space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫