989. Integer addition in array form

Title Requirements:

For the non negative integer x, the array form of X is an array formed by each number from left to right. For example, if X = 1231, its array form is [1,2,3,1].
Given the array form A of non negative integer X, return the array form of integer X+K.

Example 1:

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

Example 2:

Input: A = [2,7,4], K = 181
Interpretation: 274 + 181 = 455

Example 3:

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

Example 4:

Input: A = [9,9,9,9,9,9,9,9,9,9], K = 1
Explanation: 999999999 + 1 = 10000000000


This topic is divided into three steps:
Calculate the number of digits of the given K value, compare it with the number of elements of the original array, and determine the length of the new array in turn.
The newly developed array adds one to the maximum array length after comparison, which eliminates the problem that the array may cross the boundary later. It wastes the memory of the heap area to reduce the complexity of the code. Later, it does not need realloc() to increase the capacity of the developed array.
For example:
A=[9,9,9], K=1. The maximum length after comparing digits is 3, while 999 + 1 is 1000. It contains four elements, and the array will cross the boundary (please refer to example 4 for details).
After determining the length of the newly opened array, the next step is to add by bits, and store the bits of the added result in the opened array in order. Remember to set a carry in it, and the initial value is bit 0. The judgment condition of the whole cycle is len – (len is the result of the maximum value after comparing the number of array elements with the number of digits), that is, the larger length of the array after comparing with the number of digits is successively reduced by one digit until it is 0, jumping out of the cycle.
For example: A=[2,7,4], K=181
(1) Take out the last bit of the array 4, add the 1 obtained by K%10 and the variable controlling the carry to 5, judge whether it is greater than 9, and put it into the area where the subscript of the array is 0, subtract 1 from the subscript of the array, and K/10 obtains 18
(2) Take out the value 7 corresponding to the index of the array at this time and add it to the 8 obtained by K%10 to 15. Judge whether it is greater than 9. If it is greater than 9, subtract 10, set the variable controlling carry to 1, and put the result after subtracting 10 into the open area with the index of the array as 1. Subtract 1 from the index of the array and get 1 from K/10
(3) Take out the number corresponding to the subscript at this time as 2, add the 1 obtained by K%10 to the variable controlling the carry to 4, judge whether it is greater than 9, and put it into the area with the subscript of the opened array as 2, subtract the subscript of the array by 1, obtain 0 by K/10, and set the variable controlling the carry to 0.
exceptional case:
Case 1: A=[9,9], K=1233
At this time, the maximum length len of the array is 4, but when len is reduced by 1, array A may cross the boundary, so the subscript of the control array is greater than or equal to 0.
Case 2: A=[9,9,9], K=1
After the loop ends, the variable controlling carry is 1, but it is [0,0,0] in the array. Therefore, after the loop ends, it is necessary to judge whether the value of the variable controlling carry at this time is 1. If it is 1, it will be placed in the space with subscript i in the array at this time.
Invert the elements in the array obtained in 2.
For example: A=[2,7,4], K=181. After the steps in 2, the final array is [5,5,4].
We want to reverse it to [4,5,5]. The process of this step can be well understood by looking at the code. I won't repeat it here.

Code implementation:

int* addToArrayForm(int* A, int ASize, int K, int* returnSize){
    //1. Calculate the number of digits of K
    int Ksize=0;
    int Knum=K;

    //2. Determine the length of the array after addition, add at the end, and store the calculation results in the retArr array in order
    int len = ASize > Ksize ? ASize : Ksize;
    //Here, an additional int position is added to the array. In order to prevent more than one bit after the two are added, there is no need to increase the capacity later
    int* retArr = (int*)malloc(sizeof(int)*(len+1));
    int Ai = ASize-1;
    int Nextnum=0; //Carry operation
    int i = 0;
        //This step is to eliminate the following situations
        //When [9,9] is in array A and K=1233, the traversal starts from the end of the array. If the subscript is not controlled to be greater than or equal to, the array will be out of bounds
        int a = 0;
        if(Ai >= 0)
            a = A[Ai];

        int ret = a + K%10 + Nextnum;

        //Judge whether the number added from the end is greater than 9 and greater than carry
            ret -= 10;
            Nextnum = 1;
            Nextnum = 0;
        retArr[i] = ret;

    //Here is to judge the situation similar to 999 + 1
    if(Nextnum == 1)
        retArr[i] = 1;

    //3. Invert array
    int left = 0;
    int right = i-1;
    while(left < right)
        int tmp = retArr[left];
        retArr[left] = retArr[right];
        retArr[right] = tmp;

    *returnSize = i;
    return retArr;

I hope my blog can help you.

Source: LeetCode
Link: https://leetcode-cn.com/problems/add-to-array-form-of-integer
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.

Tags: data structure C

Posted by marcel on Tue, 19 Apr 2022 07:18:49 +0930