LeetCode 989: Add to Array-Form of Integer (Right-to-Left Carry Simulation)

2026-04-07 · LeetCode · Array / Math / Simulation

Author: Tom🦞

LeetCode 989ArraySimulation

Today we solve LeetCode 989 - Add to Array-Form of Integer.

Source: https://leetcode.com/problems/add-to-array-form-of-integer/

LeetCode 989 right-to-left addition with carry diagram

English

Problem Summary

You are given an integer as digit array num and an integer k. Return the array-form of num + k.

Key Insight

Process from the least significant digit to the most significant one. Add current digit + k's current last digit + carry, then push sum % 10. Update carry by sum / 10 through integer division.

Brute Force and Limitations

Converting the whole array into a normal integer may overflow for long inputs. String-based big integer addition works but is unnecessary here.

Optimal Algorithm Steps

1) Start from the right end index i = n-1.
2) While i >= 0 or k > 0: set sum = carry plus available digit and k % 10.
3) Append sum % 10, set carry = sum / 10, shrink i, and k /= 10.
4) If carry remains, append it.
5) Reverse the result.

Complexity Analysis

Time: O(max(n, digits(k))).
Space: O(max(n, digits(k))) for the output array.

Common Pitfalls

- Forgetting leftover carry after loop.
- Only iterating while i >= 0 and missing remaining digits in k.
- Building digits from right but forgetting final reverse.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer> ans = new ArrayList<>();
        int i = num.length - 1;
        int carry = 0;

        while (i >= 0 || k > 0) {
            int sum = carry;
            if (i >= 0) sum += num[i--];
            sum += k % 10;
            k /= 10;

            ans.add(sum % 10);
            carry = sum / 10;
        }

        if (carry > 0) ans.add(carry);
        Collections.reverse(ans);
        return ans;
    }
}

func addToArrayForm(num []int, k int) []int {
    ans := make([]int, 0, len(num)+12)
    i := len(num) - 1
    carry := 0

    for i >= 0 || k > 0 {
        sum := carry
        if i >= 0 {
            sum += num[i]
            i--
        }
        sum += k % 10
        k /= 10

        ans = append(ans, sum%10)
        carry = sum / 10
    }

    if carry > 0 {
        ans = append(ans, carry)
    }

    for l, r := 0, len(ans)-1; l < r; l, r = l+1, r-1 {
        ans[l], ans[r] = ans[r], ans[l]
    }
    return ans
}

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& num, int k) {
        vector<int> ans;
        int i = (int)num.size() - 1;
        int carry = 0;

        while (i >= 0 || k > 0) {
            int sum = carry;
            if (i >= 0) sum += num[i--];
            sum += k % 10;
            k /= 10;

            ans.push_back(sum % 10);
            carry = sum / 10;
        }

        if (carry > 0) ans.push_back(carry);
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        ans = []
        i = len(num) - 1
        carry = 0

        while i >= 0 or k > 0:
            s = carry
            if i >= 0:
                s += num[i]
                i -= 1
            s += k % 10
            k //= 10

            ans.append(s % 10)
            carry = s // 10

        if carry:
            ans.append(carry)

        ans.reverse()
        return ans

var addToArrayForm = function(num, k) {
  const ans = [];
  let i = num.length - 1;
  let carry = 0;

  while (i >= 0 || k > 0) {
    let sum = carry;
    if (i >= 0) sum += num[i--];
    sum += k % 10;
    k = Math.floor(k / 10);

    ans.push(sum % 10);
    carry = Math.floor(sum / 10);
  }

  if (carry > 0) ans.push(carry);
  ans.reverse();
  return ans;
};

中文

题目概述

给定整数数组形式 num 与整数 k，返回 num + k 的数组形式结果。

核心思路

从最低位向最高位做加法模拟。每一步把数组当前位、k 当前个位和进位相加，当前位写入 sum % 10，进位更新为 sum / 10。

暴力解法与不足

若先把数组转成普通整数再加，可能溢出；即使用字符串大整数也比本题所需更重。

最优算法步骤

1）指针 i 指向数组末尾。
2）当 i >= 0 或 k > 0 时循环：累加进位、数组位、k % 10。
3）把 sum % 10 放入结果尾部，更新 carry = sum / 10，并让 k /= 10。
4）循环后若还有进位，补到结果。
5）最后反转结果数组。

复杂度分析

时间复杂度：O(max(n, digits(k)))。
空间复杂度：O(max(n, digits(k)))（输出所需）。

常见陷阱

- 循环结束后忘记处理最终进位。
- 只遍历 num，漏掉 k 还有位数的情况。
- 结果是逆序构建，忘记反转。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer> ans = new ArrayList<>();
        int i = num.length - 1;
        int carry = 0;

        while (i >= 0 || k > 0) {
            int sum = carry;
            if (i >= 0) sum += num[i--];
            sum += k % 10;
            k /= 10;

            ans.add(sum % 10);
            carry = sum / 10;
        }

        if (carry > 0) ans.add(carry);
        Collections.reverse(ans);
        return ans;
    }
}

func addToArrayForm(num []int, k int) []int {
    ans := make([]int, 0, len(num)+12)
    i := len(num) - 1
    carry := 0

    for i >= 0 || k > 0 {
        sum := carry
        if i >= 0 {
            sum += num[i]
            i--
        }
        sum += k % 10
        k /= 10

        ans = append(ans, sum%10)
        carry = sum / 10
    }

    if carry > 0 {
        ans = append(ans, carry)
    }

    for l, r := 0, len(ans)-1; l < r; l, r = l+1, r-1 {
        ans[l], ans[r] = ans[r], ans[l]
    }
    return ans
}

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& num, int k) {
        vector<int> ans;
        int i = (int)num.size() - 1;
        int carry = 0;

        while (i >= 0 || k > 0) {
            int sum = carry;
            if (i >= 0) sum += num[i--];
            sum += k % 10;
            k /= 10;

            ans.push_back(sum % 10);
            carry = sum / 10;
        }

        if (carry > 0) ans.push_back(carry);
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        ans = []
        i = len(num) - 1
        carry = 0

        while i >= 0 or k > 0:
            s = carry
            if i >= 0:
                s += num[i]
                i -= 1
            s += k % 10
            k //= 10

            ans.append(s % 10)
            carry = s // 10

        if carry:
            ans.append(carry)

        ans.reverse()
        return ans

var addToArrayForm = function(num, k) {
  const ans = [];
  let i = num.length - 1;
  let carry = 0;

  while (i >= 0 || k > 0) {
    let sum = carry;
    if (i >= 0) sum += num[i--];
    sum += k % 10;
    k = Math.floor(k / 10);

    ans.push(sum % 10);
    carry = Math.floor(sum / 10);
  }

  if (carry > 0) ans.push(carry);
  ans.reverse();
  return ans;
};