Add to Array-Form of Integer
Add k digit-by-digit from the LSB end, mixing in k's digits via carry.
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#
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; }};func addToArrayForm(num []int, k int) []int { out := []int{} i := len(num) - 1 for i >= 0 || k > 0 { x := 0 if i >= 0 { x = num[i] i-- } s := x + (k % 10) k /= 10 k += s / 10 out = append(out, s%10) } for l, r := 0, len(out)-1; l < r; l, r = l+1, r-1 { out[l], out[r] = out[r], out[l] } return out}from typing import List
class Solution: def addToArrayForm(self, num: List[int], k: int) -> List[int]: out: List[int] = [] i = len(num) - 1 while i >= 0 or k > 0: x = num[i] if i >= 0 else 0 s = x + (k % 10) k //= 10 k += s // 10 out.append(s % 10) i -= 1 out.reverse() return outvar addToArrayForm = function(num, k) { const out = []; let i = num.length - 1; while (i >= 0 || k > 0) { const x = i >= 0 ? num[i--] : 0; const s = x + (k % 10); k = Math.floor(k / 10); k += Math.floor(s / 10); out.push(s % 10); } return out.reverse();};class Solution { public List<Integer> addToArrayForm(int[] num, int k) { LinkedList<Integer> out = new LinkedList<>(); int i = num.length - 1; while (i >= 0 || k > 0) { int x = i >= 0 ? num[i--] : 0; int s = x + (k % 10); k /= 10; k += s / 10; out.addFirst(s % 10); } return out; }}function addToArrayForm(num: number[], k: number): number[] { const out: number[] = []; let i = num.length - 1; while (i >= 0 || k > 0) { const x = i >= 0 ? num[i--] : 0; const s = x + (k % 10); k = Math.floor(k / 10); k += Math.floor(s / 10); out.push(s % 10); } return out.reverse();}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#
Related#