Leetcode-898 Add to Array-Form of Integer

Posted on Edited on In ,

Description

For a non-negative integer X, the array-form of X is an array of its digits in left to right order. For example, if X = 1231, then the array form is [1,2,3,1].

Given the array-form A of a non-negative integer X, return the array-form of the integer X+K.

Example 1:

1
2
3
Input: A = [1,2,0,0], K = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

Example 2:

1
2
3
Input: A = [2,7,4], K = 181
Output: [4,5,5]
Explanation: 274 + 181 = 455

Example 3:

1
2
3
Input: A = [2,1,5], K = 806
Output: [1,0,2,1]
Explanation: 215 + 806 = 1021

Example 4:

1
2
3
Input: A = [9,9,9,9,9,9,9,9,9,9], K = 1
Output: [1,0,0,0,0,0,0,0,0,0,0]
Explanation: 9999999999 + 1 = 10000000000

Note：

  1. 1 <= A.length <= 10000
  2. 0 <= A[i] <= 9
  3. 0 <= K <= 10000
  4. If A.length > 1, then A[0] != 0

分析

给一个数组形式的整数 X 和一个整数 K，求 X+K，其中 X 和 K 都是五位数以内的整数，所以无需考虑溢出。

拆解 K 成 Array-Form 类型得到一个整数，然后两个数组末位对齐，逐位相加即可。

拆解 K 的过程可以取余，余数与 X 的末位相加即可

1
2
3
4
while (K != 0) {
    r = K % 10;
    K = K / 10;
}

程序设计

根据上述分析，代码实现如下，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public List<Integer> addToArrayForm(int[] A, int K) {
        int carry = 0;
        for(int i = A.length-1; i >= 0; i--){
            if (K!=0) {
                int a = K%10;
                int b = A[i];
                int sum = a + b + carry;
                carry = sum / 10;
                A[i] = sum % 10;
                K /= 10;
            } else {
                int sum = A[i] + carry;
                if( sum < 10) {
                    A[i] = sum;
                    carry = 0;
                    break;
                } else {
                    A[i] = sum % 10;
                    carry = 1;
                }
            }
        }
        
        List<Integer> ans = new ArrayList<>();
        if(K != 0) {
            K += carry;
            Stack<Integer> stack = new Stack<>();
            
            while(K != 0) {
                stack.push(K % 10);
                K /= 10;
            }
            while(!stack.isEmpty()) {
                ans.add(stack.pop());
            }
        } else if(carry == 1) {
            ans.add(1);
        }
        for(int i = 0; i < A.length; i++) {
            ans.add(A[i]);
        }
        return ans;
    }
}