989. Add to Array-Form of Integer

Problem Statement

link: LeetCode.cn LeetCode

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:

Input: num = [1,2,0,0], k = 34 Output: [1,2,3,4]

Input: num = [2,7,4], k = 181 Output: [4,5,5]

Input: num = [2,1,5], k = 806 Output: [1,0,2,1]

Solution Approach

The algorithm adds the integer k to the array-form of num by processing digits from the end and handling carry-over in-place, ensuring a time complexity of O(N) and space complexity of O(N).

Algorithm

1. In-place Modification: The algorithm modifies the array num in-place by iterating from the end to the beginning, handling carry-over directly within the array.
2. Carry Handling: If there is a carry left after processing all digits, it is converted to a string, mapped to a list of its digits, and prepended to the result, ensuring proper digit placement.
3. Efficient Handling: This method processes each digit at most twice (once for addition and once for carry propagation), achieving a time complexity of O(N) and a space complexity of O(N), where N is the length of the resulting array.

Complexity

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

Implement

    class Solution:
      def addToArrayForm(self, num: List[int], k: int) -> List[int]:
          num[-1] += k
          n = len(num)
          for i in range(n - 1, -1, -1):
              carry, num[i] = divmod(num[i], 10)
              if carry == 0:
                  break
              if i:
                  num[i - 1] += carry
          if carry:
              num = list(map(int, str(carry))) + num

          return num
              
 

    
    

Twitter  facebook  Email