989. Add to Array-Form of Integer
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 45.0%
Problem Breakdown
The problem requires adding an integer k to an integer represented in its array form. The array form of an integer is a list of digits where each element represents a digit in the number, starting from the most significant digit.
Inputs:
num: A list of integers representing the digits of a number.k: An integer that needs to be added to the number represented bynum.
Outputs:
- A list of integers representing the array form of the sum of
numandk.
Implicit Constraints or Tricky Edge Cases:
- The length of
numcan be up to 10,000 digits. kcan also be quite large, up to 10,000.- There are no leading zeros in the array form except for the number zero itself.
Intuition
A brute-force approach would involve converting the entire array-form number into a single integer, adding k, and then converting it back into an array. However, this approach is inefficient due to potential overflow issues with large numbers and high time complexity (O(n) where n is the length of the array).
The key insight is to simulate the addition process digit by digit from right to left, similar to how manual addition works. This way, we can handle each digit individually, taking care of carry-over values as needed.
Approach
- Initialize an empty list
resultto store the digits of the final sum. - Use a variable
carryinitialized to 0 to keep track of any carry-over from adding two digits. - Iterate over the array-form number
numin reverse order (from least significant digit to most significant). - For each digit, add it along with the current value of
kand thecarry. - Compute the new digit to be added to the result list as
(current_sum % 10). - Update the
carryas(current_sum // 10). - After processing all digits in
num, continue adding any remaining carry-over fromkuntil there is no more carry. - Reverse the
resultlist to get the final array-form number.
Complexity Analysis
- Time Complexity: O(max(n, log(k))), where n is the length of the array-form number and log(k) is the number of digits in k. This is because we iterate over each digit in both the array and the integer.
- Space Complexity: O(max(n, log(k))) for storing the result.
Solution
def addToArrayForm(num, k):
result = []
carry = 0
# Iterate over num from right to left
i = len(num) - 1
while i >= 0 or k > 0:
current_digit = num[i] if i >= 0 else 0
total_sum = current_digit + (k % 10) + carry
# Append the new digit to the result
result.append(total_sum % 10)
# Update carry and reduce k
carry = total_sum // 10
k //= 10
i -= 1
# If there's any remaining carry, add it to the result
if carry:
result.append(carry)
# Reverse the result to get the correct order
return result[::-1]
Edge Cases Handled
- Large
k: The solution handles cases wherekis larger than the number represented bynum. - Carry-over: Handles cases where adding two digits results in a carry that needs to be propagated.
- All 9s in
num: For example, ifnum = [9,9,9]andk = 1, the result should be[1,0,0,0]. - Single-digit
num: Handles cases wherenumhas only one digit. - Zero as input: If
num = [0]andk = 0, the result is[0].