Welcome to Subscribe On Youtube

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;
    }
};


  • 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;
    }
}

############

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        int i = num.length - 1, carry = 0;
        LinkedList<Integer> ans = new LinkedList<>();
        while (i >= 0 || k > 0 || carry > 0) {
            carry += (i < 0 ? 0 : num[i--]) + k % 10;
            ans.addFirst(carry % 10);
            carry /= 10;
            k /= 10;
        }
        return ans;
    }
}

  • // OJ: https://leetcode.com/problems/add-to-array-form-of-integer/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<int> addToArrayForm(vector<int>& A, int K) {
        int N = A.size(), carry = 0;
        vector<int> ans;
        for (int i = N - 1; i >= 0 || K || carry;) {
            if (K) {
                carry += K % 10;
                K /= 10;
            }
            if (i >= 0) carry += A[i--];
            ans.push_back(carry % 10);
            carry /= 10;
        }
        reverse(begin(ans), end(ans));
        return ans;
    }
};

  • class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        i, carry = len(num) - 1, 0
        ans = []
        while i >= 0 or k or carry:
            carry += (0 if i < 0 else num[i]) + (k % 10)
            carry, v = divmod(carry, 10)
            ans.append(v)
            k //= 10
            i -= 1
        return ans[::-1]

############

class Solution(object):
    def addToArrayForm(self, num, k):
        p1 = len(num) - 1
        carry = 0
        res = []
        while p1 >= 0 or k != 0 or carry > 0:
            adder1 = num[p1] if p1 >= 0 else 0
            adder2 = k % 10
            sum = adder1 + adder2 + carry
            carry = 1 if sum >= 10 else 0
            sum = sum - 10 if sum >= 10 else sum
            res.append(sum)
            p1 -= 1
            k //= 10
        return res[::-1]

  • func addToArrayForm(num []int, k int) []int {
	i, carry := len(num)-1, 0
	ans := []int{}
	for ; i >= 0 || k > 0 || carry > 0; i-- {
		if i >= 0 {
			carry += num[i]
		}
		carry += k % 10
		ans = append(ans, carry%10)
		carry /= 10
		k /= 10
	}
	for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
		ans[i], ans[j] = ans[j], ans[i]
	}
	return ans
}

  • function addToArrayForm(num: number[], k: number): number[] {
    let arr2 = [...String(k)].map(Number);
    let ans = [];
    let sum = 0;
    while (num.length || arr2.length || sum) {
        let a = num.pop() || 0,
            b = arr2.pop() || 0;
        sum += a + b;
        ans.unshift(sum % 10);
        sum = Math.floor(sum / 10);
    }
    return ans;
}


  • impl Solution {
    pub fn add_to_array_form(num: Vec<i32>, mut k: i32) -> Vec<i32> {
        let n = num.len();
        let mut res = vec![];
        let mut i = 0;
        let mut sum = 0;
        while i < n || sum != 0 || k != 0 {
            sum += num.get(n - i - 1).unwrap_or(&0);
            sum += k % 10;
            res.push(sum % 10);

            i += 1;
            k /= 10;
            sum /= 10;
        }
        res.reverse();
        res
    }
}

All Problems

All Solutions