Add To Array Form Of Integer - Leetcode Solution

Problem Statement:

The problem statement asks the user to perform a special kind of addition operation on an array and a given integer. Given an array of non-negative integers and an integer K, the task is to add the integer K to the array in such a way that the addition operation is performed in the same way as we perform the arithmetic addition operation.

Solution:

The problem statement is straight forward. We have an array of integers and we have to add the integer K to it. But the tricky part here is to get the result in the same representation as that of the normal addition operation. To achieve this, we can perform the addition from the right side of the array (least significant digit) and take the carry forward element and add to the next element.

Algorithm:

1. Initialize a carry variable as 0.
2. Traverse the array from the rightmost element to left and repeat step 3 to 5 until all the elements are traversed.
3. Add the K to the last element of the array and the carry from step 4.
4. Divide the result from step 3 by 10 to get the carry for next iteration and update the carry variable with this value.
5. Append the remainder from step 3 to the list of output elements.
6. Reverse the list of output elements as we performed the operation from the rightmost element.

Code:

def addToArrayForm(A, K):
        
    # initialize a variable to store carry
    carry = 0
        
    # initialize an empty list to store output
    output = []
        
    # iterate the list from right to left
    for i in range(len(A) - 1, -1, -1):
            
        # add the K and carry to the last element of the list
        temp = A[i] + K % 10 + carry
            
        # get the carry for next iteration
        carry = temp // 10
            
        # append the remainder to the list of output elements
        output.append(temp % 10)
            
        # remove the last digit from K
        K = K // 10
        
    # if there is any carry left, append it to the output list
    if carry:
        output.append(carry)
        
    # reverse the output list and return it
    return output[::-1]

Time Complexity:

The time complexity of the above algorithm will be O(n) where n is the length of the array. Since we are iterating the array only once from right to left, the time complexity will be linear in the size of the input.

Space Complexity:

The space complexity of the above algorithm will also be O(n), as we are creating an output list of length n to store the result.

1