Question

Formatted question description: https://leetcode.ca/all/989.html

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:

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

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

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

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 <= A.length <= 10000
0 <= A[i] <= 9
0 <= K <= 10000
If A.length > 1, then A[0] != 0


Algorithm 1

This question is given to an array A, saying that it can represent a positive integer, the high bit is at the beginning, and a positive number K is given, adding K to the positive integer represented by the array A, and also using the array to represent the addition After the result.

This kind of addition problem with different data structures has appeared before, such as Add Two Numbers, Plus One, Add Binary, and Add Strings. But in fact, all changes are inseparable. They all need to be added one by one, and the problem of carry is handled.

Here, since the high bit is at the beginning of the array, and the addition starts from the low bit, so start traversing from the back of the array, add K with the current bit number, and then take the remainder of 10, and the result is the addition The number on the digit. You may be worried about the carry issue. The result of the carry will be added to K and will not be lost. At this time, K plus A[i] should also be divided by 10, and then continue to loop. After the array A is traversed, K may still be greater than 0. At this time, the K value should be added to the front in the form of an array. Each time the remainder of 10 is added to the beginning of the result res, and then K is divided by 10 Yes, see the code as follows:

Code 1

C++

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& A, int K) {
        vector<int> res;
        for (int i = (int)A.size() - 1; i >= 0; --i) {
            res.insert(res.begin(), (A[i] + K) % 10);
            K = (A[i] + K) / 10;
        }
        while (K > 0) {
            res.insert(res.begin(), K % 10);
            K /= 10;
        }
        return res;
    }
};

Algorithm 2

We can also do it with just one loop and update the array A directly without using the additional array. Then the loop condition is that K is greater than 0, or the carry value is greater than 0. In the loop, let carry plus K to take the remainder of 10. If the value of array A has not been traversed yet, that is, if i is greater than or equal to 0, add A[i], and then divide num by 10. It is the updated carry value, and the remainder of 10 is the current value. At this time, if i is greater than or equal to 0, update A[i] to the value of num, and decrement i by 1, otherwise add num to the beginning of array A, then divide K by 10, and finally return to array A, see code show as below:

Code 2

C++

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& A, int K) {
		int n = A.size(), i = n - 1, carry = 0;
		while (K > 0 || carry > 0) {
			int num = K % 10 + carry;
			if (i >= 0) num += A[i];
			carry = num / 10;
			num %= 10;
			if (i >= 0) {
				A[i] = num;
				--i;
			} else {
				A.insert(A.begin(), num);
			}
			K /= 10;
		}
		return A;
    }
};

Java

class Solution {
    public List<Integer> addToArrayForm(int[] A, int K) {
        List<Integer> sum = new ArrayList<Integer>();
        int length = A.length;
        A[length - 1] += K;
        for (int i = length - 1; i > 0; i--) {
            int curNum = A[i];
            if (curNum >= 10) {
                A[i - 1] += curNum / 10;
                A[i] %= 10;
            }
        }
        char[] highestArray = String.valueOf(A[0]).toCharArray();
        for (char c : highestArray) {
            int digit = c - '0';
            sum.add(digit);
        }
        for (int i = 1; i < length; i++)
            sum.add(A[i]);
        return sum;
    }
}

All Problems

All Solutions