989. Add to Array-Form of Integer
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
(or0
if we've passed the beginning ofnum
), the last digit ofk
, 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 arrayans
. - Update the value of
k
to reflect the leftover part after extracting the last digit by performing integer division by10
. - 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.
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:
-
Initialize the index
i
to point to the last digit of the input arraynum
which represents the least significant digit of the number we are given. Also, initialize acarry
variable to0
, which will keep track of any carryover during the addition process. -
Create an empty list
ans
that will store the result of the addition in reverse order. -
Execute a
while
loop with the condition to continue as long as there is a digit remaining in thenum
array (i >= 0
), or there is still a part ofk
that hasn't been added (k
), or there is a carry from the previous addition (carry
). -
The sum for the current position is calculated by adding the current digit of
num
array, if any (num[i]
or0
ifi
is less than0
), the last digit ofk
(k % 10
), and the currentcarry
. This is done using the line:carry += (0 if i < 0 else num[i]) + (k % 10)
-
The
carry
and the value to append to the result list,v
, are determined by usingdivmod()
:carry, v = divmod(carry, 10)
This operation returns the quotient that becomes the next
carry
and the remainderv
which is the digit to be appended to the answer. -
Append
v
to theans
list:ans.append(v)
-
The next digit of
k
is obtained by reducingk
by one decimal place using the floor division operation:k //= 10
-
Decrement the index
i
to move the pointer to the left, preparing for the next iteration to add the next higher order digit. -
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 reverseans
to correct the order:return ans[::-1]
-
Return the reversed
ans
list as the final output, which now represents thenum + 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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
-
Initialize the index
i
to2
since the last digit ofnum
is at index2
. Also, thecarry
variable is initialized to0
. -
An empty list
ans
is created to store the result. -
Enter the
while
loop which continues as long asi >= 0
,k > 0
, orcarry
is not0
. -
In the first iteration,
i
is2
, there is no carry, andk
is34
. So, we calculate:carry += num[2] + k % 10 # carry += 6 + 4
carry
now becomes10
. The next step is to split this intocarry
andv
:carry, v = divmod(10, 10) # carry = 1, v = 0
We append
0
toans
(sincev = 0
) and adjustk
andi
:k //= 10 # k becomes 3 i -= 1 # i becomes 1
-
The next iteration starts with
i = 1
,carry = 1
, andk = 3
. The sum is:carry += num[1] + k % 10 # carry += 5 + 3
carry
now becomes9
. Again, we split this intocarry
andv
:carry, v = divmod(9, 10) # carry = 0, v = 9
We append
9
toans
and adjustk
andi
:k //= 10 # k becomes 0 i -= 1 # i becomes 0
-
The final iteration starts with
i = 0
,carry = 0
, andk = 0
. We perform the addition:carry += num[0] + k % 10 # carry += 2 + 0
carry
now becomes2
. Split intocarry
andv
:carry, v = divmod(2, 10) # carry = 0, v = 2
We append
2
toans
:ans.append(v)
-
The loop finishes since
i
is now less than0
,k
is0
, andcarry
is also0
. The result listans
is currently[0, 9, 2]
. -
We reverse
ans
to get the correct order:ans[::-1] # becomes [2, 9, 0]
-
The final output is
[2, 9, 0]
, which is the correct array representation of256 + 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
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.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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
Want a Structured Path to Master System Design Too? Donāt Miss This!