Add to Array-Form of Integer
EasyPrompt
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 = 1234Example 2:
Input: num = [2,7,4], k = 181
Output: [4,5,5]
Explanation: 274 + 181 = 455Example 3:
Input: num = [2,1,5], k = 806
Output: [1,0,2,1]
Explanation: 215 + 806 = 1021
Constraints:
1 <= num.length <= 1040 <= num[i] <= 9numdoes 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
LinkedListfor the result. - Initialize a pointer
ito the last index ofnum. - Loop as long as
iis valid (>= 0) ork > 0. - Inside the loop, if
iis valid, addnum[i]tok. - Add the last digit of the current sum (
k % 10) to the front of the result list. - Update
kto 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:
- Initialize a
LinkedListto store the result digits. ALinkedListis chosen for its efficient O(1)addFirstoperation, which avoids a final reversal step. - Start a loop that continues as long as there are digits left in
numto process ork(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
numat the current position, add it tok. - The current digit for the result is
k % 10. - The new carry is
k / 10. We updatekto this value for the next iteration. - Prepend the current digit (
k % 10) to the result list. - Move to the next digit in
numby decrementing the pointer. - After the loop, the
LinkedListcontains 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
BigIntegerobjects, reducing overhead.Demonstrates a fundamental understanding of arithmetic operations.
Cons
Slightly more complex to implement correctly compared to the
BigIntegerapproach.
This approach converts the input array num into a BigInteger object, adds k to it, and then converts the resulting BigInteger back into an array of digits. It leverages Java's built-in library for handling arbitrarily large integers.
Algorithm
- Convert the
numarray to a string. - Create a
BigIntegerfrom the string representation ofnum. - Create a
BigIntegerfrom the integerk. - Add the two
BigIntegerobjects. - Convert the resulting
BigIntegersum back to a string. - Create a new list and populate it with the digits from the sum string.
- Return the list.
Walkthrough
The core idea is to delegate the complex arithmetic of large numbers to the java.math.BigInteger class, which is designed for this purpose.
Algorithm Steps:
- Convert the
numarray into its string representation. For example,[1,2,0,0]becomes"1200". - Create a
BigIntegerinstance from this string. - Create another
BigIntegerinstance from the integerk. - Use the
add()method ofBigIntegerto compute the sum. - Convert the resulting
BigIntegersum back to a string. - Iterate through the characters of the result string, convert each character to its numeric value, and add it to a list.
- Return the final list of digits.
import java.math.BigInteger;import java.util.ArrayList;import java.util.List; class Solution { public List<Integer> addToArrayForm(int[] num, int k) { // 1. Convert num array to a string StringBuilder sb = new StringBuilder(); for (int digit : num) { sb.append(digit); } String numStr = sb.toString(); // 2. Create BigInteger objects and add them BigInteger numBigInt = new BigInteger(numStr); BigInteger kBigInt = BigInteger.valueOf(k); BigInteger sumBigInt = numBigInt.add(kBigInt); // 3. Convert the sum back to a string String sumStr = sumBigInt.toString(); // 4. Convert the sum string to a list of integers List<Integer> result = new ArrayList<>(); for (char c : sumStr.toCharArray()) { result.add(c - '0'); } return result; }}Complexity
Time
O(N + M), where N is the length of `num` and M is the number of digits in the sum. This is because converting the array to a string takes O(N), `BigInteger` operations take time proportional to the number of digits, and converting the final string to a list takes O(M). Since M is approximately max(N, log10(k)), the complexity is O(N).
Space
O(N + M), for storing the string representations and the final result list, where N is the length of `num` and M is the number of digits in the sum. This simplifies to O(N).
Trade-offs
Pros
Simple to implement if you are familiar with the
BigIntegerclass.Reduces the chance of implementation errors in the arithmetic logic by using a well-tested library.
Cons
Less efficient due to the overhead of creating multiple intermediate objects (StringBuilder, BigInteger, String).
Involves multiple data type conversions which can be slow.
May not be what an interviewer is looking for, as it abstracts away the core addition logic.
Solutions
Solution
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; }}class Solution {public: vector<int> addToArrayForm(vector<int> &num, int k) { int i = num.size() - 1, carry = 0; vector<int> ans; for (; i >= 0 || k || carry; --i) { carry += (i < 0 ? 0 : num[i]) + k % 10; ans.push_back(carry % 10); carry /= 10; k /= 10; } reverse(ans.begin(), ans.end()); return ans; }};class Solution: def addToArrayForm(self, num: List[int], k: int) -> List[int]: i, carry = len(num) - 1, 0 ans = [] while i >= 0 or k or carry: carry += (0 if i < 0 else num[i]) + (k % 10) carry, v = divmod(carry, 10) ans . append(v) k //= 10 i -= 1 return ans[:: - 1]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.