azl397985856 commented 3 years ago

989. 数组形式的整数加法

入选理由

暂无

题目地址

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

前置知识

数组的遍历

题目描述


对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。

给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。

示例 1：

输入：A = [1,2,0,0], K = 34 输出：[1,2,3,4] 解释：1200 + 34 = 1234 示例 2：

输入：A = [2,7,4], K = 181 输出：[4,5,5] 解释：274 + 181 = 455 示例 3：

输入：A = [2,1,5], K = 806 输出：[1,0,2,1] 解释：215 + 806 = 1021 示例 4：

输入：A = [9,9,9,9,9,9,9,9,9,9], K = 1 输出：[1,0,0,0,0,0,0,0,0,0,0] 解释：9999999999 + 1 = 10000000000

提示：

1 <= A.length <= 10000 0 <= A[i] <= 9 0 <= K <= 10000 如果 A.length > 1，那么 A[0] != 0

ruohai0925 commented 3 years ago

思路

从个位开始加，用carry表示进位

关键点

代码

语言支持：Python3

Python3 Code:

# from typing import List
from collections import deque
class Solution:
    def addToArrayForm(self, A, K):
        if K == 0:
            return A

        i = len(A) - 1
        carry = 0

        # d = []
        d = deque()

        while i >= 0 and K > 0:
            temp = A[i] + carry + K % 10
            #d.insert(0, temp % 10)
            d.appendleft(temp % 10)
            carry = temp // 10
            K = K // 10
            i -= 1

        while i < 0 and K > 0:
            temp = K % 10 + carry
            #d.insert(0, temp % 10)
            d.appendleft(temp % 10)
            carry = temp // 10
            K = K // 10

        while i >= 0:
            temp = A[i] + carry
            #d.insert(0, temp % 10)
            d.appendleft(temp % 10)
            carry = temp // 10
            i -= 1

        if carry > 0:
            #d.insert(0, carry)
            d.appendleft(carry)

        #return d
        return list(d)

复杂度分析

令 n 为数组长度。

时间复杂度：$O(n)$
空间复杂度：$O(n)$

ImSingee commented 3 years ago

impl Solution {
    pub fn add_to_array_form(num: Vec<i32>, mut k: i32) -> Vec<i32> {
        let mut result = Vec::new();
        for i in (0..num.len()).rev() {
            result.push({
                let result = num[i] + k;
                let x = result % 10;
                k = result / 10;
                x
            })
        }

        while k > 0 {
            result.push({
                let x = k % 10;
                k = k / 10;
                x
            })
        }

        result.reverse();
        result
    }
}

复杂度分析

时间复杂度 O(len(num)) [logk约等于1 忽略] 额外空间复杂度 O(1)

lilyzhaoyilu commented 3 years ago

思路

按照官方题解

CPP代码

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& num, int k) {
        vector<int> res;
        int n = num.size();
        for(int i = n - 1; i >= 0; --i){
            int curSum = num[i] + k % 10;
            k /= 10;
            if(curSum >= 10){
                k++;
                curSum -=10;
            }
            res.push_back(curSum);
        }
        while(k > 0){
            res.push_back(k % 10);
            k /= 10;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

复杂度分析

时间复杂度：O(n + logk + resLength)，其中 n 为数组的长度；resLength是res这个vector的长度，来自于reverse的时间消耗
空间复杂度：O(1)

Dana-Dai commented 3 years ago

思路

直接对数组操作，但要注意进位，尤其是K > A的情况，要在数组开头插入以进位

语言

cpp

代码

··· class Solution { public: vector addToArrayForm(vector& num, int k) { //把K直接加到数组num上 int len = num.size() - 1; while (k > 0) { num[len] += k; k = num[len] / 10; num[len] %= 10; len --;

        if (len < 0 && k > 0) {
            num.insert(num.begin(), 0);
            len = 0;
        }
    }
    return num;
}

};


## 复杂度分析
时间复杂度：$O（N）$即需要遍历一遍数组，故为N
空间复杂度：$O（1）$不需要额外开辟空间

last-Battle commented 3 years ago

思路

关键点

从个位开始往前面推算，每计算一位就放入vector结果中，并通过carry维护进位，最后再反转
注意数组下标和k的位数要保证有效，防止越界

代码

语言支持：C++

C++ Code:


class Solution {
public:
    vector<int> addToArrayForm(vector<int>& num, int k) {
        vector<int> res;
        int carry = 0, len = num.size() - 1;
        int tmparr = 0, tmpk = 0, sum = 0;
        int i = len;
        while (i >= 0 || k != 0) {
            tmparr = 0;
            tmpk = 0;
            if (k != 0) {
                tmpk = k % 10;
                k /= 10;
            }
            if (i >= 0) {
                tmparr = num[i];
                --i;
            }

            sum = tmparr + tmpk + carry;
            carry = sum / 10;
            res.emplace_back(sum % 10);    
        }

        if (carry) {
            res.emplace_back(carry);
        }

        reverse(res.begin(), res.end());

        return res;
    }
};

复杂度分析

令 n 为数组长度。

时间复杂度：$O(n)$
空间复杂度：$O(n)$

mm12344 commented 3 years ago

思路

简单数值解法

代码

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        x = 0
        ans=[]
        if len(num)==1 and num[0]==0 and k==0: return[0]
        for i in num:
            x = x*10 + i
        x = x + k
        while x!=0:
            ans.append(x%10)
            x=x//10
        return ans[::-1]

复杂度

时间：O(2n) 空间：O(ans)

wangzehan123 commented 3 years ago

代码

语言支持：Java

Java Code:


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

复杂度分析

令 n 为数组长度。

时间复杂度：$O(max(n,logk))$
空间复杂度：$O(1)$

erik7777777 commented 3 years ago

思路

从低位往高位顺着加

代码： java

public List<Integer> addToArrayForm(int[] num, int k) {
        int carry = 0;
        List<Integer> res = new ArrayList<>();
        int i = num.length - 1;
        while (i >= 0 || k > 0) {
            int cur = (i >= 0 ? num[i] : 0) + (k > 0 ? k % 10 : 0) + carry;
            k = k > 0 ? k / 10 : 0;
            i = i >= 0 ? i - 1 : -1;
            carry = cur / 10;
            cur = cur % 10;
            res.add(cur);
        }
        if (carry == 1) res.add(carry);
        Collections.reverse(res);
        return res;
    }

复杂度分析

时间复杂度：O(n)，其中 n 为数组的长度
空间复杂度：O(1)

yachtcoder commented 3 years ago

从低到高递归处理每一位以及前面的进位

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        num = num[::-1]
        k = [int(x) for x in str(k)][::-1]
        ret = []
        def add1(l1, l2, carry, idx):
            nonlocal ret
            if carry == 0 and idx >= len(l1) and idx >= len(l2): return
            n1 = 0 if idx >= len(l1) else l1[idx]
            n2 = 0 if idx >= len(l2) else l2[idx]
            ret.append((n1+n2+carry) % 10)
            carry = (n1+n2+carry)//10
            add1(l1, l2, carry, idx+1)
        add1(num, k, 0, 0)
        return ret[::-1]

Time: O(n) Space: O(n)

chang-you commented 3 years ago

代码

Java:

// Space = O(n) / O(1) 数组/k长度
// Time = O(Math.max(n, log(k)) / O(1): num或k长度中较大的
class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        //用LinkedList不断从头将位数和加入index 0
        List<Integer> res = new LinkedList<>();
        int n = num.length;
        for (int i = n - 1; i >= 0; i--) {
            //从末尾往前扫，加和取余的值
            res.add(0, (num[i] + k) % 10);
            //更新k存进位carry
            k = (num[i] + k) / 10;
        }

        // post-possing: 处理k位数大于num的情况剩下的部分
        // Time = O(log(k))
        while (k > 0) {
            res.add(0, k % 10);
            k /= 10;
        }

        return res;
    }
}

复杂度分析

Space = O(n) / O(1) ：数组/k长度

Time = O(Math.max(n, log(k)) / O(1): num或k长度中较大的

mmboxmm commented 3 years ago

思路

Addition from right to left

代码

fun addToArrayForm(num: IntArray, k: Int): List<Int> {
  val res = mutableListOf<Int>()
  var carry = 0
  var index = num.size - 1
  var tmp = k

  while (index >= 0 || tmp > 0 || carry > 0) {
    var sum = carry
    if (index >= 0) sum += num[index--]
    if (tmp > 0) sum += tmp % 10

    res.add(sum % 10)

    carry = sum / 10
    tmp /= 10
  }
  return res.reversed()
}

// No / and %
fun addToArrayForm2(num: IntArray, k: Int): List<Int> {
  val res = mutableListOf<Int>()
  val arr = k.toString().map { it - '0' }
  var carry = 0

  for (i in 1..maxOf(num.size, arr.size)) {
    val sum = carry + num.getOrElse(num.size - i) { 0 } + arr.getOrElse(arr.size - i) { 0 }

    carry = if (sum >= 10) {
      res.add(sum - 10)
      1
    } else {
      res.add(sum)
      0
    }
  }
  if (carry == 1) res.add(1)
  return res.reversed()
}

复杂度分析

Time：O(len(num))
Space：O(1)

wangwiitao commented 3 years ago

JS

var addToArrayForm = function (num, k) {
    const ret = [];
    let i = num.length - 1, carry = 0;
    while (i >= 0 || k != 0) {
        let x = i >= 0 ? num[i] : 0;
        let y = k !== 0 ? k % 10 : 0;

        const sum = x + y + carry;

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

        i--;
        k = Math.floor(k / 10);
    }
    if (carry) {
        ret.push(carry);
    }
    return ret.reverse();
};

复杂度分析

时间复杂度：O（n），再具体不会了
空间复杂度：O（1）

leungogogo commented 3 years ago

LC989. Add to Array-Form of Integer

Main Idea

First, it looks like we can convert the array num to integer and add it to k, but num.length <= 1E+4 so this approach will cause integer overflow. So we will have to do the addition in array form.

Then the idea is to simulate the entire process, add each digit of num and k with a carry bit. We will terminate the loop when we run out of digits for both num and k and carry == 0.

Code

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

        while (i >= 0 || k > 0 || carry > 0) {
            int kDigit = k % 10;
            k /= 10;
            int sum = i >= 0 ? carry + kDigit + num[i] : carry + kDigit;
            res.add(sum % 10);
            carry = sum >= 10 ? 1 : 0;
            --i;
        }

        Collections.reverse(res);
        return res;
    }
}

Complexity Analysis

Time: O(2*max(N, log(K)))

Given a number K, its length will be O(log_{2}(K)), the time complexity depends on the length of N and K, whichever is longer.
Notice we want to insert digits at the end of the array and then reverse it after we finish the addition (reverse takes O(res.size())). If we insert at the head of array, then it will take O(n^2) of time.

Space: O(1), as we didn't use additional spaces except the return array.

ai2095 commented 3 years ago

LC 989 Add to Array-Form of Integer

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

Topics

Array
Math

思路

Add the number K to the array from right to left.

代码 Python

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        carrier = 0
        num_len = len(num)
        i = num_len -1
        # Add all matching digit        
        while i >= 0 and k > 0:
            cur_k, k = k%10, k//10
            t_carrier = (num[i] + cur_k + carrier) // 10
            num[i] = (num[i] + cur_k + carrier) % 10
            carrier = t_carrier
            i -= 1

        # Check whether num or k is left
        if i >= 0:
            while i >= 0:
                t_carrier = (num[i] + carrier) // 10
                num[i] = (num[i] + carrier) % 10
                carrier = t_carrier
                if carrier == 0:
                    break
                i -= 1

        if k > 0:
            while k > 0:
                cur_k, k = k%10, k//10
                t_carrier = (cur_k + carrier) // 10
                num = [(cur_k + carrier) % 10] + num
                carrier = t_carrier

        # Deal with carrier
        if carrier > 0:
            return [carrier] + num
        else:
            return num

复杂度分析

时间复杂度：O(N)
空间复杂度：O(1)

yanglr commented 3 years ago

思路

双指针 + 进位加法逻辑

双指针, 让两个数的末位对齐, 两个指针 i, j均从各自字符串的末尾开始走。

定义一个数组来存放结果, 一个int值carry来记录每位的进位值, 初始值设为0。算当前位置的数时, sum = a[i] + b[j] + carry, 每趟都要记得更新carry的值。

循环结束时, 由于低位的数字字符先加到了结果字符串中, 最后还需要 reverse 一次, 让位置恢复正常。

代码

实现语言: C++

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& A, int k) {
        if (k == 0) return A;
        vector<int> res;
        int n = A.size();
        // 对位相加
        int carry = 0;
        int sum = 0;      
        int i = n - 1; 
        while (k > 0 || i >= 0)
        {
            sum = carry + (k % 10);
            if (i >= 0) // 保证访问A[i]前不越界
                sum += A[i];

            carry = (sum <= 9) ? 0 : 1;
            res.push_back(sum % 10);            
            k = k / 10;

            i--;
        }
        if (carry == 1) res.push_back(1);
        reverse(res.begin(), res.end());
        return res;
    }
};

代码已上传到: leetcode-ac/91algo - github.com

复杂度分析

时间复杂度：O(max(n, k))，其中 n 为数组长度, k为数K的长度。
空间复杂度：O(n), 主要是结果数组用的空间

ZiyangZ commented 3 years ago

Talk about how to make an easy problem complicated:

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        int size = Math.max(num.length, String.valueOf(k).length());
        int dif = size - num.length; 
        int[] ans = new int[size];
        int carry = 0;
        for (int i = ans.length - 1; i >= 0; i--) {
            int n = (i - dif) < 0 ? 0:num[i - dif];
            int m = k % 10;
            k = k / 10;
            ans[i] = (n + m + carry) % 10;
            carry = (n + m + carry) / 10;
        }

        List<Integer> list = new ArrayList<>();
        if (carry == 1) list.add(1);
        for (int i: ans) list.add(i);

        return list;
    }
}

So turns out all we need to do is adding digits from the last position and reverse the list.
Time and space O(max(n, m)) where n is the length of num and m is the number of digits in k.

cicihou commented 3 years ago

class Solution(object):
    def addToArrayForm(self, num, k):
        """
        :type num: List[int]
        :type k: int
        :rtype: List[int]
        """
        res = []
        for i in num:
            res.append(str(i))
        res = str(int(''.join(res)) + k)
        res = [int(i) for i in res]
        return res

time: O(n) space: O(n)

shixinlovey1314 commented 3 years ago

Title:989. Add to Array-Form of Integer

Question Reference LeetCode

Solution

Revert the array, so that we only need to manipulate the end of the array.
Extract the lowest digit of K and add into the array ascendingly.
After each addition, if the item at the given index excceds 10, then only keep the lowest digit part and add 1 to the next item in the array (Watch out the array boundary and expand the array by 1 if needed..
After processed K, check if there still exist delta > 0, if so keep on repeating the process similar to step 2 until delta equals 0.
Revert the array back.

Code

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& num, int k) {
        int index = 0;
        int delta = 0;

        std::reverse(num.begin(), num.end());

        while (k > 0) {
            delta += k % 10 + num[index];
            k /= 10;

            num[index++] = delta % 10;
            delta /= 10;

            if (index == num.size() && (k > 0 || delta > 0))
                num.push_back(0);
        }

        while (delta > 0) {
            delta += num[index];
            num[index++] = delta % 10;
            delta /= 10;

            if (index == num.size() && (delta > 0))
                num.push_back(0);
        }

        std::reverse(num.begin(), num.end());

        return num;
    }
};

Complexity

Time Complexity and Explaination

O(max(N, M)), N is the size of the array, while M is the size of the virtual array form of K, which is logarithm of base 10 -> log10(K).

Space Complexity and Explaination

O(1) since we reuse the input array and didn't need any extra space

pangjiadai commented 3 years ago

思路

模版

while ( A 没完 || B 没完)
    A 的当前位
    B 的当前位

    和 = A 的当前位 + B 的当前位 + 进位carry

    当前位 = 和 % 10;
    进位 = 和 / 10;

判断还有进位吗

代码

语言： Python3

from collections import deque
class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        i = len(num) -1
        res = []
        carry = 0

        while i >=0 or k != 0:
            if i >= 0:
                curr_num = num[i]
            else:
                curr_num = 0
            if k != 0:
                curr_k = k % 10 
            else:
                curr_k = 0

            total = curr_num + curr_k + carry
            curr_total = total % 10
            carry = total // 10
            res.append(curr_total)
            i -= 1
            k = k // 10

        if carry != 0:
            res.append(carry)

        return res[::-1]

复杂度：

时间复杂度：$O(n)$ 遍历
空间复杂度：$O(n)$ 新创立了一个ans list

nonevsnull commented 3 years ago

思路

Deque, Array遍历；

注意题目要求，1 <= A.length <= 10000，所以直接做加法是不可能的。

代码

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        int pos = 0;
        int carry = 0;
        Deque<Integer> res = new LinkedList<>();
        while(pos < num.length || k >= Math.pow(10, pos) || carry > 0){
            int fromNum = pos < num.length?num[num.length - 1 - pos]:0;
            int fromK = (k / (int)Math.pow(10, pos)) % 10;
            int sum = fromNum + fromK + carry;
            res.addFirst(sum % 10);
            carry = sum > 9?1:0;
            pos++;
        }

        return new ArrayList<>(res);
    }
}

复杂度

k因为是常数，其长度可以忽略。

O(num.length) O(1)

yiwchen commented 3 years ago

思路： add with carry

Python:

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        res = []
        n = len(num)
        while(n > 0 or k > 0):
            if n > 0:
                k += num[n - 1]
            k, r = divmod(k, 10)
            res.append(r)
            n -= 1
        return res[::-1]

C++:

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

            /*Calculation of current digit*/

            sum = num[i] + k % 10;
            k /= 10;

            /*Add the carry to k if there is any*/

            if (sum >= 10){
                k++;
                sum -= 10;
            }

            /*Append the sum to the end*/

            res.push_back(sum);
        }

        /* Append the rest of k to the end if k is bigger than n*/

        for (k = k; k > 0; k/= 10){
            res.push_back(k % 10);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

复杂度分析:

时间复杂度：O(len(A) + len(str(k)) + len(res)) = O(max(len(A), len(str(k)))) 空间复杂度：O(1)

qixuan-code commented 3 years ago

LC 989. Add to Array-Form of Integer

思路

把num list转化成数字
数字和k相加
相加的和转化成list

python代码

    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        n = len(num)
        true_number = 0
        result = []
        if k == 0 and len(num) == 1:
            return num
        for i in range(n):
            true_number = true_number + num[i]*10**(n-i-1)

        add_up = true_number + k
        while add_up:
            result.append(add_up%10)
            add_up = add_up//10

        return result[::-1]

复杂度分析

时间复杂度：O(N)
空间复杂度：O(N)

JiangyanLiNEU commented 3 years ago

Two ideas hit me when I saw this problem.

convert array num to integer --> add k to the integer --> convert new integer to array --> return this array
Use k as carry on number, and keep adding it to the elements in num until k is 0. Note that, we might need to insert elements into num array.

Here is my implement:

Convert idea ( Runtime = O( len(num) ), Space = O( len(num) ) )

class Solution(object):
def addToArrayForm(self, num, k):
    # convert array num into string version
    num_string = ''
    for n in num:
        num_string += str(n)

    # add num and k, and convert it to string version
    num_add_k_string = str(int(num_string) + k)

    # convert result into array of int version
    toReturn = [ int(i) for i in num_add_k_string ]
    return toReturn

carry k idea ( Runtime = O( len(num) ), Space = O(1) )

class Solution(object):
def addToArrayForm(self, num, k):
    # add k into the last digit of num, and check if there should be a carryOn number
    num[-1] += k
    if num[-1] < 10:
        return num
    # if no carryOn number, then just return num, otherwise, we keep adding carry on into previous digit and update carryOn
    carryOn = num[-1]//10
    num[-1] = num[-1]%10
    index = -2
    while carryOn != 0:
        # when there are enough digits for us to add
        if index >= -len(num):
            num[index] += carryOn
        # we need to insert new digit at the beginning of the array
        else:
            num.insert(0, carryOn)
        carryOn = num[index] // 10
        num[index] %= 10
        index -= 1
    return num

ZT4188 commented 3 years ago

思路：历遍数组

Python: class Solution: def addToArrayForm(self, A: List[int], K: int) -> List[int]: K = list(map(int,str(K)))

    res = []
    i,j = len(A)-1,len(K)-1
    carry = 0

    while i >= 0 and j >= 0:
        res.append(A[i] + K[j] + carry)
        res[-1],carry = res[-1] % 10, res[-1] // 10
        i -= 1
        j -= 1
    while i >= 0:
        res.append(A[i] + carry)
        res[-1],carry = res[-1] % 10, res[-1] // 10
        i -= 1
    while j >= 0:
        res.append(K[j] + carry)
        res[-1],carry = res[-1] % 10, res[-1] // 10
        j -= 1

    if carry:
        res.append(1)

    return res[::-1]

时间复杂度：O(N+max(0,K−N) 空间复杂度：O(1)

Jackielj commented 3 years ago

LC 989. Add to Array-Form of Integer

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

时空复杂度：

时间：O(Math.max(len(num), len(k.toString()))

空间：O(1)

Daniel-Zheng commented 3 years ago

思路

从末位开始，向vector里添加各对应位置数字与进位之和。如原数组里各位置已加完，则需处理K中剩余数字与进位之和。

代码(C++)

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& num, int k) {
        int carry = 0;
        vector<int> res;
        for (int i = num.size() - 1; i >= 0; i--) {
            res.push_back((carry + num[i] + k % 10) % 10);
            carry = (carry + num[i] + k % 10) / 10;
            k /= 10;
        }
        carry = carry + k;
        while (carry) {
            res.push_back(carry % 10);
            carry /= 10;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

复杂度分析

时间复杂度：O(N + logN + Max(0, K - N)^2)，N为数组A的长度，K为K的长度。
空间复杂度：O(Max(1, K - N))，N为数组A的长度，K为K的长度。

thinkfurther commented 3 years ago

思路

从后往前加，直到没有为止

代码(Python3)

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        carry = 0
        add1 = 0
        add2 = 0
        stop1Flag = False
        stop2Flag = False

        resultStack = []

        k_int = list(map(int,str(k)))

        index = -1
        while(True):
            try:
                add1 = num[index]                
            except:
                stop1Flag = True
                add1 = 0

            try:
                add2 = k_int[index]
            except:
                stop2Flag = True
                add2 = 0

            index -= 1

            if(stop1Flag and stop2Flag):
                if carry != 0:
                    resultStack.append(carry)
                break
            else:
                resultStack.append((add1 + add2 + carry)%10)
                carry = (add1 + add2 + carry)//10
        return (list(resultStack[::-1])

复杂度分析

时间复杂度：O(N + Max(0, K - N)^2)，N为数组A的长度，K为K的长度。空间复杂度：O(Max(1, K + N))，N为数组A的长度，K为K的长度。

RonghuanYou commented 3 years ago

按照加法的运算顺序从后往前遍历，r是余数，也就是做完加法后的当前位的值 k是除去最后一位的值结束循环，如果k>0，就要一直处理最后的carry，就是k%10放入output array

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        sumArr = []
        for i in range(len(num) - 1, -1, -1):
            r = (num[i] + k) % 10
            k = (num[i] + k) // 10
            sumArr.append(r)

        while k > 0:
            sumArr.append(k % 10)
            k = k // 10
        return sumArr[::-1]

pophy commented 3 years ago

Java代码

    public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer> res = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        int borrow = 0;
        int i = num.length - 1;

        while (k != 0 || i >= 0 || borrow != 0) {
            int currentNumber;
           if (i >= 0 && k != 0) {
                currentNumber = num[i] + k % 10;
           } else if (i >=0) {
               currentNumber = num[i];
           } else {
               currentNumber = k % 10;
           }
            stack.add((currentNumber + borrow) % 10);
            borrow = (currentNumber + borrow) / 10;
            k = k / 10;
            i--;
        }

        while (!stack.isEmpty()) {
            res.add(stack.pop());
        }
        return res;
    }

时间复杂度

O(n)

空间复杂度

O(n)

ninghuang456 commented 3 years ago

JAVA code:

class Solution {
    public List<Integer> addToArrayForm(int[] A, int K) {
        LinkedList<Integer> res = new LinkedList<>();
        int carry = 0;
        int index = A.length - 1;
        while(K > 0 || index >= 0){
            int curK = K % 10;
            int curA = index >= 0 ? A[index]: 0;
            int curDigitSum = curK + curA + carry;
            int toBeAdded = curDigitSum % 10;
            carry = curDigitSum / 10;
            index --;
            K /= 10;
            res.addFirst(toBeAdded);
        }
        if(carry != 0){
            res.addFirst(1);
        }
        return res;
    }
}

Time: O(n); Space: O(n);

zol013 commented 3 years ago

Python 3 code:

class Solution:
     def addToArrayForm(self, num: List[int], k: int) -> List[int]:
          if num[0] == 0 and k == 0:
             return [0]
          inputnum = 0
          for number in num:
               inputnum = inputnum * 10 + number
          summ = inputnum + k 
          res = []
          while summ > 0:
                  digit = summ % 10
                  res.append(digit)
                  summ = summ // 10
          return res[::-1]

Time Complexity: O(n) because we run through the given array one time Space Complexit: O(n) because we created a new array res to record the sum

qyw-wqy commented 3 years ago

代码

Java:

 public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer> list = new ArrayList<>();
        int i = num.length-1;
        int carry = k;
        while (i >= 0 || carry > 0) {
            int n = i >= 0 ? num[i--] : 0;
            carry += n;
            list.add(carry % 10);
            carry /= 10;
        }

        Collections.reverse(list);
        return list;
    }

Time：O(n)
Space：O(n)

skinnyh commented 3 years ago

Solution1

Use while loop to add K to num digit by digit. Maintain the carry and end the loop when carry is 0 and all digits from K has been added. Note that inserting to the list head is not efficient.

Code

    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        carry, idx = 0, len(num) - 1
        while k > 0 or carry > 0:
            digit = k % 10
            k = k // 10
            if idx < 0:
                num.insert(0, 0)
                i = 0
            else:
                i = idx
            tmp = num[i] + digit + carry
            num[i] = tmp % 10
            carry = tmp // 10
            idx -= 1
        return num

Time complexity: O(N + max(0, K - N)^2), K is length of k and N is length of num

Space complexity: O(max(1, K - N))

Solution2

Create another result array and always append the digit sum to the result end to avoid insert to head. Reverse the result list before return. The while loop end condition will also need to check if it has traversed all the num list.

Code

    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        carry, idx = 0, len(num) - 1
        res = []
        while idx >= 0 or k > 0 or carry > 0:
            digit = k % 10
            k = k // 10
            n = num[idx] if idx >= 0 else 0
            res.append((n + digit + carry) % 10)
            carry = (n + digit + carry) // 10
            idx -= 1
        return reversed(res)

Time complexity: O(N)

Space complexity: O(N)

leo173701 commented 3 years ago

很笨的办法，请忽略
时间复杂度 o(n), 空间复杂度o(n)

`def addToArrayForm(self, num: List[int], k: int) -> List[int]:

    n = len(num)
    temp = 0
    for i in range(n):
        temp +=num[i]* (10**(n-1-i))     
    b = temp + k
    res = []
    while b>9:
        d = b%10
        b = b//10
        res.append(d)
    res.append(b)
    res.reverse()        
    return res`

kidexp commented 3 years ago

Thinking

assume num length is n, k has m digits

Take [1,2,3]+999 as an example

First convert [1,2,3] into 123 which takes O(m)

Then add 123 with 999 = 1122, which takes O(1)

Finally convert 1122 to [1,1,2,2] which is O(max(m,n)+1) = O(max(m,n)

Code

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        m = 0
        for digit in num:
            m = m * 10 + digit
        sum_ = m + k
        result = []
        while sum_:
            result.append(sum_ % 10)
            sum_ //= 10
        return result[::-1] if result else [0]

Complexity

Time: O(n)+O(1)+O(max(m,n) = O(m+n)

Space Complexity: O(max(m,n))

falconruo commented 3 years ago

思路:

数组num的第1个元素num[0]表示整数的最高位数字, 第n个元素num[n - 1]代表整数的个位数字
新的整数的每一位数字由三个部分决定：num[i], 整数k的当前位(k % 10), 进位(carry)->sum = val + k % 10 + carry

复杂度分析:

时间复杂度: O(max(N, lgk))，N为数组num的长度, k为给定整数k
空间复杂度: O(1)

代码(C++):

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& num, int k) {
        int n = num.size() - 1;
        vector<int> res;
        int carry = 0, val = 0, sum = 0;
        while (n >= 0 || k != 0) {
            val = (n >= 0) ? num[n] : 0;
            sum = val + k % 10 + carry;
            res.push_back(sum % 10);
            carry = sum / 10;
            k /= 10;
            n--;
        }

        if (carry)
            res.push_back(carry);

        reverse(res.begin(), res.end());

        return res;
    }
};

florenzliu commented 3 years ago

Explanation

Convert k to its array-form.
Add the array-forms of num and k by digit from the end to the beginning and save it in the result array.
Reverse the array-form of the result.

Use the quotient and remainder divided by 10: set the current position as the remainder and update the quotient for the next position.

Python

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        newK = []
        for i in str(k):
            newK.append(int(i))

        result = []
        i, j = len(num)-1, len(newK)-1
        quotient, remainder = 0, 0
        while i >= 0 or j >= 0:
            currI = num[i] if i >= 0 else 0
            currJ = newK[j] if j >= 0 else 0
            curr = currI + currJ + quotient
            result.append(curr % 10)
            quotient = curr // 10
            i -= 1
            j -= 1

        if quotient != 0:
            result.append(quotient)
        return result[::-1]

Complexity

Time Complexity: O(max(N, logk)) where N is the length of the num array.
Space Complexity: O(max(N, logk))

q815101630 commented 3 years ago

Ripple Adder

Similar to the implementation of ripple adder, The adder will add numbers at the same position, output the sum of the current position, and pass the carry to the next bit.

Python

class Solution:
    def addToArrayForm(self, A: List[int], k: int) -> List[int]:
        curSum = 0
        carry = 0

        # This can be achieved through continuing division, but I am lazy
        if not A:
            return [int(i) for i in str(k)]
        elif not k:
            return A

        K = [int(i) for i in str(k)]
        LA = len(A)-1
        LK = len(K)-1

        if LA <= LK:
            target = K
            idx = LK
        else:
            target = A
            idx = LA
        while LA >= 0 and LK >= 0:
            curSum = A[LA] + K[LK] + carry
            if curSum < 10:
                target[idx] = curSum
                carry = 0
            else:
                carry = curSum //10
                target[idx] = curSum % 10
            LA-=1
            LK-=1
            idx-=1
        if LK != LA:
            while idx >=0:
                curSum = target[idx] + carry
                if curSum < 10:
                    target[idx] = curSum
                    carry = 0
                else:
                    carry = curSum // 10
                    target[idx] = curSum%10
                idx-=1
        if carry > 0:
            target[0:0] = [carry]
        return target

Time Complexity: O(max(K,A)) Space Complexity: O(max(K,A))

xixvtt commented 3 years ago

989. Add to Array-Form of Integer

想法：最brutal way： traverse list->str->int->list then after reviewing others knowing this way could cause the overflow trying to update the new ones later

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        str_turple = ''
        for i in num:
            str_turple += str(i)

        str_int = int(str_turple) + k
        int_str = str(str_int)

        output = []
        for n in int_str:
            output.append(int(n))
        return output

complexcity O(n^2)

ZhuMengCheng commented 3 years ago

思路: 从末尾相加后截取末尾存储进位,, 测试用例: [2,1,5] 806 比如806和5相加等于811 ,保存末尾1, 继续相加为81+1=82. 保存2 类推, 8会和下一个2相加为10, 整个数组的值变成[10,2,1] 截取10的情况,可能计算次数超过数组长度.需要添加额外条件判断计算次数

var addToArrayForm = function(num, k) {
    let res = []
    // k>0 如果遇到合为10需要多一次计算 ,查询条件不能限制为只有num数组的长度
    for(let i = num.length-1 ;i>=0 || k > 0;--i){
        // 大于0的位数直接相加后取余数进位
        if(i >= 0){
            k += num[i]
        }
        res.push(k % 10)
            // 计算是否有等于10 或者大于0的情况,在执行下次进位
            k = (k - k % 10) / 10
        }
        return res.reverse()
}

时间复杂度：O(max(n,log k)) 空间复杂度: O(n)

chen445 commented 3 years ago

思路:

First, we should convert k to list and iterate from back of the list. If the sum of two digits at the same position plus carry is greater than 10, then we set the carry to 1. The modulo of the sum is the result at that position.

代码：

  def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        k=[int(x) for x in str(k)]
        i=len(num)-1
        j=len(k)-1
        carry=0
        result=deque([])
        while i>=0 or j>=0:
            a=num[i] if i >=0 else 0 
            b=k[j] if j>=0 else 0
            s=a+b+carry
            carry=s//10
            result.appendleft(s%10)
            i-=1
            j-=1
        if carry != 0:
            result.appendleft(carry)
        return result

复杂度分析

Time Complexity: O(n) n is the largest length of two numbers

Space Complexity: O(n)

JachinM commented 3 years ago

Java

解题思路

整型数组开始与k相应的位上的数字相加（从个位开始，整型数组的个位是num[num.length-1]），并将每位上相加的结果添加到一个整型的Array数组中。
这里需要注意如果相对应位置上的数相加大于10时，我们应该有进位操作，即让k+1，number-10（ps：这里的number代表整型数组与k的相应位置上的数相加后得到的结果）
最后如果k>0,这说明最高位上有进位，最后得到的数组少最高位，我们应该再把k的每个位置的数取出来加入到数组中。

由于低数位先加入我们最终得到的Array数组中，所以我们需要翻转一下得到的数组，在java中可以调用Collections.reverse()函数来实现。

class Solution {
public List<Integer> addToArrayForm(int[] num, int k) {
    int len = num.length;
    List<Integer> resultList = new ArrayList<>();
    int sum =0;
    for(int i=len-1;i>=0;i--){
        sum = num[i]+k%10;
        k=k/10;
        if(sum>=10){
            k++;
            sum-=10;
        }
        resultList.add(sum);
    }
    while(k>0){
        resultList.add(k%10);
        k=k/10;
    }
    Collections.reverse(resultList);
    return resultList;
}
}

时间复杂度

O(n)

空间复杂度

O(n)

zhangyalei1026 commented 3 years ago

思路

convert a list of integers into a number update this number by adding k convert back the result into a list of integers

代码

def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        num_str = ""
        for n in num:
            num_str += str(n)
        output = []
        for n in str(int(num_str) + k):
            output.append(int(n))
        return output

复杂度分析 Time Complexity：O(n) Space Complexity：O(n)

zhangzz2015 commented 3 years ago

思路

把K按照位转换成vector。则求解方法和求解两个vector 数相加相同，从后往前遍历。注意carry。时间复杂度 k的位数N，A的位数位M, O(N) + O(max(N,M)) 空间复杂度为 O(N + max(N,M))

class Solution { public: vector addToArrayForm(vector& num, int k) {

    vector<int> veck;  
    while(k)
    {
        veck.push_back(k%10);
        k =k /10; 
    }
    bool next = false; 
    int left =num.size()-1; 
    int right =0; 
    vector<int> ret; 
    while(left>=0 && right < veck.size())
    {
        int sum = num[left] + veck[right] + (next? 1:0);
        if(sum/10)
            next = true; 
        else
            next = false; 
        sum = sum%10; 
        ret.push_back(sum);    
        left--; 
        right++; 
    }
    while(left>=0)
    {
        int sum = num[left] + (next? 1:0); 
        if(sum/10)
            next = true; 
        else
            next = false; 
        sum = sum%10; 
        ret.push_back(sum);    
        left--;                 
    }
    while(right < veck.size())
    {
        int sum = veck[right] + (next? 1 : 0);
        if(sum/10)
            next = true; 
        else
            next = false; 
        sum = sum%10; 
        ret.push_back(sum);    
        right++;             
    }
    if(next)
        ret.push_back(1);
    reverse(ret.begin(), ret.end());
    return ret;
}

};



**复杂度分析**

令 n 为数组长度。

- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$

zhangzz2015 commented 3 years ago

思路

考虑k的大小很小，可以不用转换按照位存储，直接原地转换。时间复杂度O(N) 空间复杂度 O(N)

代码

语言支持：C++

C++ Code:


class Solution {
public:
    vector<int> addToArrayForm(vector<int>& num, int k) {
/// consider k         
     int left = num.size()-1; 
     int cur = k;    
     vector<int> ret; 
     while( left>=0 || cur )
     {
         if(left>=0)
             cur = cur + num[left]; 

         ret.push_back(cur%10);
         cur = cur/10; 
         left--;
     }
     reverse(ret.begin(), ret.end());
        return ret; 
    }   
};

复杂度分析

令 n 为数组长度。

时间复杂度：$O(n)$
空间复杂度：$O(n)$

tongxw commented 3 years ago

思路

while num[i]存在或者 k不为0: 当前位sum = 进位 + numsi + k mod 10 (如果k不为0)；倒序遍历num，同时k = k /10; 进位 carry = sum / 10; 当前位 digit = sum mod 10; 输出数组记录digit; 如果最后一位有进位，添加到输出数组中;

代码

/**
 * @param {number[]} num
 * @param {number} k
 * @return {number[]}
 */
var addToArrayForm = function(num, k) {
    i = num.length - 1;
    carry = 0;
    ans = [];
    while(i >= 0 || k != 0) {
      sum = carry;
      if (i >= 0) {
        sum += num[i];
        i--;
      }
      if (k != 0) {
        sum += k % 10;
        k = Math.floor(k / 10);
      }

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

    if (carry > 0) {
      ans.unshift(carry);
    }

    return ans;
};

复杂度分析

时间复杂度：O(N)，其中 N 为数组长度。 k <= 10^4 不计
空间复杂度：O(N)，其中 N 为数组长度。

okbug commented 3 years ago

JS 占坑其实可以用力扣第二题（两数之和）类似的解法

var addToArrayForm = function(num, k) {
    let res = [];
    for (let i = num.length - 1; i >= 0 || k > 0; i--) {

        if (i >= 0) {
            k += num[i];
        }

        res.push(k % 10); // 当时个位上的数
        k = (k - k % 10) / 10;
    }

    return res.reverse();
}

yanglr commented 3 years ago

思路

按照官方题解

CPP代码

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& num, int k) {
        vector<int> res;
        int n = num.size();
        for(int i = n - 1; i >= 0; --i){
            int curSum = num[i] + k % 10;
            k /= 10;
            if(curSum >= 10){
                k++;
                curSum -=10;
            }
            res.push_back(curSum);
        }
        while(k > 0){
            res.push_back(k % 10);
            k /= 10;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

复杂度分析

时间复杂度：O(n + logk + resLength)，其中 n 为数组的长度；resLength是res这个vector的长度，来自于reverse的时间消耗
空间复杂度：O(1)

结果数组的空间复杂度是O(n), 除非你就在原数组上做操作总的空间复杂度才是O(1)吧

yan0327 commented 3 years ago

思路： 1.数组从个位开始[即从后往前计数]，用一个sum保存位和[加数+被加数+低位进位],一个pre保存进位重新设置一个输出数组out。 2.数组从后往前遍历，每位与k%10相加、与低位进位相加，获得sum 。 sum%10加入数组，sum/10为进位值，运算完记得把k/10. 3.若数组跑完k还有值或进位有值，则再跑一遍循环处理完剩余的数据 4.最后对整个数组首尾交换即可代码：

func addToArrayForm(num []int, k int) []int {
    n := len(num)
    pre := 0
    sum := 0
    out := []int{}
    for i:= n-1; i >=0||k>0||pre>0 ; i--{
        if i >= 0{
            sum = num[i]+(k%10)+pre
        }else{
            sum = k%10 +pre
        }
        pre = sum/10
        k /= 10
        out = append(out, sum%10)
    }
    reverse(out)
    return out
}

func reverse (num []int) []int{
    for i:=0; i < len(num)/2;i++{
        num[i], num[len(num)-i-1] =  num[len(num)-i-1], num[i]
    }
    return num
}

时间复杂度：O(n) 空间复杂度:O(n)

chenming-cao commented 3 years ago

解题思路

因为数组num的长度太大，会越界，所以每一数位单独运算。把k先用字符串方法转换为各个数位的数组。用carry记录进位，每一个对应数位进行加法运算，结果存到链表头部。注意循环结束后再查看一下最终进位carry是否为0，不为0的话存到链表中。

代码（java）

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        String str = String.valueOf(k); // Convert k to string, can also use Integer.toString(k)
        String[] elements = str.split(""); // Get individual digits as String format
        int klen = elements.length;

        int carry = 0;
        LinkedList<Integer> result = new LinkedList<>();
        int nlen = num.length;
        int length = nlen > klen ? nlen : klen;

        for (int i = 0; i < length; i++) {
            int knum = i < klen ? Integer.parseInt(elements[klen - 1 - i]) : 0;
            int cur = nlen - 1 - i;
            int n = i < nlen ? num[cur] : 0;
            result.addFirst((n + knum + carry) % 10);
            carry = (n + knum + carry) / 10;
        }

        if (carry != 0) result.addFirst(carry);       
        return result;
    }
}

复杂度分析

令n为nums数组长度，字符串数组的长度为logk

时间复杂度：O(max(n, logk)), 两个数组长度的最大值（最终循环次数）
空间复杂度：O(n), 创建链表储存结果

leetcode-pp / 91alg-5-daily-check

【Day 1 】2021-09-10 - 989. 数组形式的整数加法 #1

989. 数组形式的整数加法

入选理由

题目地址

前置知识

题目描述

思路

关键点

代码

复杂度分析

思路

CPP代码

复杂度分析

思路

语言

代码

思路

关键点

代码

思路

代码

复杂度

代码

思路

代码 ： java

复杂度分析

代码

复杂度分析

思路

代码

复杂度分析

JS

复杂度分析

LC989. Add to Array-Form of Integer

Main Idea

Code

Complexity Analysis

LC 989 Add to Array-Form of Integer

Topics

Similar Questions

思路

代码 Python

复杂度分析

思路

代码

实现语言: C++

复杂度分析

Title:989. Add to Array-Form of Integer

Question Reference LeetCode

Solution

Code

Complexity

Time Complexity and Explaination

Space Complexity and Explaination

思路

模版

代码

复杂度：

思路

代码

复杂度

Two ideas hit me when I saw this problem.

Here is my implement:

Convert idea ( Runtime = O( len(num) ), Space = O( len(num) ) )

carry k idea ( Runtime = O( len(num) ), Space = O(1) )

LC 989. Add to Array-Form of Integer

时空复杂度：

思路

代码(C++)

复杂度分析

思路

代码(Python3)

复杂度分析

Java代码

时间复杂度

空间复杂度

代码

Solution1

Code

代码： java