[NOTES]Day 01 - 989. Add to Array-Form of Integer

[Yufanzh]

989 Add to Array-Form of Integer

Click here to redirect to leetcode

• Title for internal link
  • Description
  • Approach 1
    • Intuition&Algorithm
    • Implementation
    • Complexity Analysis
  • Approach 2
    • Intuition&Algorithm
    • Implementation
    • Complexity Analysis

Description

The array-form of an integer num is an array representing its digits in left to right order.

For example, for num = 1321, the array form is [1,3,2,1].
Given num, the array-form of an integer, and an integer k, return the array-form of the integer num + k.

Example 1:

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

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

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

Input: num = [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
 
Constraints:

1 <= num.length <= 104
0 <= num[i] <= 9
num does not contain any leading zeros except for the zero itself.
1 <= k <= 104

Approach 1

Intuition Algorithm

in python, there is no issue with int overflow, so you can convert num to int A and perform sum = A+K, then convert the sum to a new list

Implementation

• Java code

class Solution{
}

• Python3 code

def Solution(object):
   def addtoArrayForm(self, num: List[int], k:int) -> List[int]:
        return [int(i) for i in list(str(int("".join(str(i) for i in num)) + k))]

Complexity Analysis

Time complexity: O(N)
Space complexity: O(N)

Approach 2

Intuition Algorithm

add from the last value in arraylist, let carry = sum // 10, if carry is larger than 0, we add it to the left value or add to the front.
simple idea: current value = num.current + K.current + carry

Implementation

• Java code

class Solution{
    public List<Integer> addToArrayForm(int[] num, int k) {
        //add to the end of an arraylist and then reverse it can be faster
        List<Integer> ans = new ArrayList<Integer>();
        int idx = num.length - 1;
        int sum = 0;
        int carry = 0;
        while(idx >=0 || k!=0){// condition, either of those nums has un added number
            int x = idx >=0 ? num[idx]:0;
            int y = k !=0 ? k%10 : 0;
            
            sum = x + y + carry;
            carry = sum/10;
            k = k/10;
            sum %= 10;
            
            //move idx to the left and repeat
            idx--;
            ans.add(sum);
        }
        
        //in the end, check if carry ==0
        if(carry != 0){
            ans.add(carry);
        }
        Collections.reverse(ans);
        return ans;      
    }
}

• Python3 code

def Solution(object):
       def addToArrayForm(self, num, k):
        """
        :type num: List[int]
        :type k: int
        :rtype: List[int]
        """
        K = list(map(int, str(k)))
        
        res = []
        i = len(num)-1
        j = len(K)-1
        carry = 0
        while i>= 0 or j>=0:
            x = num[i] if i>=0 else 0
            y = K[j] if j>=0 else 0
            sum = x + y + carry
            carry = sum //10
      
            i -= 1
            j -= 1
            res.append(sum%10)
            
        
        if carry !=0:
            res.append(carry)
        res.reverse()
        return res

Complexity Analysis

Time complexity: O(N)
Space complexity: O(N)