Add to Array-Form of Integer

Add k digit-by-digit from the LSB end, mixing in k's digits via carry.

Easy
Time O(n + log k) Space O(n + log k)
LeetCode
3 min read
math array

Problem#

A big integer is given as a digit array (MSB first). Add k and return the new digit array.

Examples#

  • [1,2,0,0], k=34[1,2,3,4].
  • [2,7,4], k=181[4,5,5]; [9,9,9,9,9,9,9,9,9,9], k=1[1,0,0,0,0,0,0,0,0,0,0].

Constraints#

  • 1 <= num.length <= 10^4, 0 <= k <= 10^4.

Approach#

Walk num from the back, adding the LSB of k plus carry. Continue with k > 0 even after num is exhausted; reverse at the end.

Solution#

Add to Array-Form of Integer
class Solution {
public:
vector<int> addToArrayForm(vector<int>& num, int k) {
vector<int> out;
int i = num.size() - 1;
while (i >= 0 || k > 0) {
int x = (i >= 0) ? num[i--] : 0;
int s = x + (k % 10);
k /= 10;
k += s / 10;
out.push_back(s % 10);
}
reverse(out.begin(), out.end());
return out;
}
};

Editorial#

Treating k as a running counter (not pre-converting to digits) keeps the code one-pass and tight — the integer’s tens digit is the natural place to stash any carry.

Complexity#

  • Time: O(n + log k).
  • Space: O(n + log k).

Concept revision#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.