Add to Array-Form of Integer — Problem & Solution
Add to Array-Form of Integer solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Add to Array-Form of Integer is an easy coding problem on arrays and math, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Easy
- Topics: Arrays, Math
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The array form of an integer is its digits listed most significant first — so 1321 is [1,3,2,1].
Given the array form of a non-negative integer num and an integer k, return the array form of 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]
Example 3
Input: num = [9,9,9,9], k = 1
Output: [1,0,0,0,0]
Explanation: The carry adds a new leading digit.
Constraints
1 <= num.length <= 100000 <= num[i] <= 9num does not contain leading zeros except when it is [0].1 <= k <= 10000
Hints for Add to Array-Form of Integer
Hint 1
The array can be 10,000 digits long, so you cannot convert it to a machine integer.
Hint 2
Do schoolbook addition from the least significant digit, carrying as you go.
Hint 3
Seed the carry with
kitself — then the whole ofkis absorbed naturally digit by digit.
How to solve Add to Array-Form of Integer
Treat k as the initial carry. Sweeping right to left, each step folds one digit of num into the carry and emits one output digit — so k is consumed without a separate loop.
Approach
- Set
carry = kand walknumfrom its last index to its first. - Add
num[i]tocarry, pushcarry % 10to the output, and setcarry = carry / 10. - After the array is exhausted, keep emitting digits while
carry > 0. - Reverse the collected digits, since they were produced least significant first.
Why it works
At every step the invariant is that the digits emitted so far plus carry · 10^emitted equals the sum of the processed suffix and k. Draining the remaining carry restores the full value.
Complexity
- Time —
O(n + log k) - Space —
O(n + log k) for the output
Pitfalls
- Parsing the array into an integer overflows every fixed-width type at 10,000 digits.
- Stopping as soon as the array ends drops the leading carry —
[9,9,9,9] + 1needs a fifth digit. - Forgetting the final reverse returns the digits backwards.
Reference solution
Python
from typing import List
def addToArrayForm(num: List[int], k: int) -> List[int]:
out = []
carry = k
for i in range(len(num) - 1, -1, -1):
carry += num[i]
out.append(carry % 10)
carry //= 10
while carry > 0:
out.append(carry % 10)
carry //= 10
out.reverse()
return outJava
public static int[] addToArrayForm(int[] num, int k) {
ArrayList<Integer> out = new ArrayList<>();
long carry = k;
for (int i = num.length - 1; i >= 0; i--) {
carry += num[i];
out.add((int) (carry % 10));
carry /= 10;
}
while (carry > 0) {
out.add((int) (carry % 10));
carry /= 10;
}
int m = out.size();
int[] res = new int[m];
for (int i = 0; i < m; i++) res[i] = out.get(m - 1 - i);
return res;
}C++
vector<int> addToArrayForm(vector<int>& num, int k) {
vector<int> out;
long long carry = k;
for (int i = (int) num.size() - 1; i >= 0; i--) {
carry += num[i];
out.push_back((int) (carry % 10));
carry /= 10;
}
while (carry > 0) {
out.push_back((int) (carry % 10));
carry /= 10;
}
reverse(out.begin(), out.end());
return out;
}JavaScript
var addToArrayForm = function(num, k) {
const out = [];
let carry = k;
for (let i = num.length - 1; i >= 0; i--) {
carry += num[i];
out.push(carry % 10);
carry = Math.floor(carry / 10);
}
while (carry > 0) {
out.push(carry % 10);
carry = Math.floor(carry / 10);
}
out.reverse();
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays