Jobs

Interviews

Discussions

Add to Array-Form of Integer

#1073 Most AskedEasy

Add to Array-Form of Integer #1073 Most Asked

Easy

Microsoft

8 views

Topics:

Arrays

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

Constraints:

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

Try coding it in LeetCode

Add to Array-Form of Integer

#1073 Most AskedEasy

Add to Array-Form of Integer #1073 Most Asked

Easy

Microsoft

8 views

Topics:

Arrays

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

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the `num` array and the value of `k`? Can `k` be negative?
Can the elements in the `num` array be negative?
If the sum results in a leading zero, should I remove it from the result?
Is the input array `num` guaranteed to be a valid array representation of a non-negative integer (e.g., no leading zeros unless the number is zero itself)?
Could `num` be an empty array?

Brute Force Solution

Approach

We're given a number as a list of digits and another number. The brute force approach is to first convert the digit list into a single big number. Then, add the two numbers together and convert the result back into a list of digits.

Here's how the algorithm would work step-by-step:

Take the digit list and combine all the digits to form one single large number.
Add the other given number to this large number to get their sum.
Break down the sum back into individual digits and create a new list of these digits. This list represents the array-form of the resulting sum.

Code Implementation

def add_to_array_form_of_integer(digit_list, number_to_add):
    # Convert the digit list into a single large number
    large_number = 0
    for digit in digit_list:
        large_number = large_number * 10 + digit

    # Add the other given number to this large number
    sum_of_numbers = large_number + number_to_add

    # Convert the sum back into a list of digits
    result_list = []
    if sum_of_numbers == 0:
        result_list.append(0)
    else:
        while sum_of_numbers > 0:
            # Extract the last digit
            digit = sum_of_numbers % 10

            result_list.append(digit)

            # Remove the last digit
            sum_of_numbers //= 10

    # Reverse the list to get the correct order
    result_list.reverse()
    return result_list

Big(O) Analysis

Time Complexity

O(n) – Converting the digit list to a single large number involves iterating through each of the 'n' digits, where 'n' is the number of digits in the input array. Adding the other number is a constant time operation. Converting the resulting sum back into a list of digits also requires, at most, iterating a number of times proportional to 'n' because the number of digits in the sum will be at most n+1 (consider 999 + 1 = 1000). Therefore, the dominant operation is the conversion to and from a single number, both of which are O(n).

Space Complexity

O(N) – The algorithm creates a new list to store the digits of the sum. The size of this list can be at most N+1, where N is the number of digits in the original input list (A). This occurs when the added number K results in a sum with one more digit than A. Therefore, the auxiliary space is proportional to the number of digits in the result, which is O(N).

Optimal Solution

Approach

Imagine adding the number K to the array as if you're doing it by hand, column by column. We start from the end and work our way to the beginning, handling any carry-over values as we go. This lets us directly construct the result without needing to convert the array into a single large number.

Here's how the algorithm would work step-by-step:

Start at the rightmost digit of the array and the rightmost digit of the number K.
Add these two digits together.
If the sum is 10 or more, keep the rightmost digit as part of the result and carry-over the '1' to the next column (just like in grade school addition).
Move to the next digit in the array (going from right to left) and the next digit of K (if K has more digits).
Repeat the addition and carry-over process.
If you run out of digits in the array but K still has digits, keep adding the digits of K along with any carry-over values.
If you run out of digits in K but the array still has digits, keep adding the digits of the array along with any carry-over values.
If there's a final carry-over value after processing all digits, add it to the beginning of the result.
The result is a new array representing the sum of the original array and the number K.

Code Implementation

def addToArrayForm(number_array, k_value):
    result_array = []
    array_length = len(number_array) - 1
    carry_over = 0

    while array_length >= 0 or k_value > 0:
        current_sum = carry_over

        if array_length >= 0:
            current_sum += number_array[array_length]
            array_length -= 1

        if k_value > 0:
            current_sum += k_value % 10
            k_value //= 10

        # If sum >= 10, we extract the digit and propagate carry.
        result_array.append(current_sum % 10)
        carry_over = current_sum // 10

    # Add any final carry to the result.
    if carry_over > 0:
        result_array.append(carry_over)

    result_array.reverse()
    return result_array

Big(O) Analysis

Time Complexity

O(max(n, logK)) – The algorithm iterates through the array A of size n and the digits of the integer K. The number of digits in K is proportional to log base 10 of K, or more generally log base b of K for some base b. Since Big O notation ignores constant factors and lower order terms, the time complexity is determined by the larger of the two values: n (the size of the array A) and logK (number of digits of K). Therefore, the dominant factor dictates the runtime.

Space Complexity

O(N) – The algorithm constructs a new list to store the result of the addition. In the worst-case scenario, where adding K to the array results in an array whose length is one greater than the original array (e.g., adding 1 to [9,9,9]), the new list will have a size proportional to the number of digits in the input array, A. If K has more digits than A, then the result's size will be proportional to the number of digits in K. Thus in the worst case the result will be proportional to the size of N = max(len(A), len(K)), where len(K) is the number of digits in K. This leads to an auxiliary space complexity of O(N).

Edge Cases

Case	How to Handle
Empty input array num	Treat an empty input array as the integer 0 and proceed with the addition with k.
k is zero	Return the original array num if k is zero, as no addition is needed.
Large value of k that results in integer overflow in intermediate calculations	Perform digit-by-digit addition and carry-over to avoid exceeding integer limits.
The input array num contains leading zeros	Remove the leading zeros from the array at the beginning or during the processing.
The sum has more digits than either k or the number represented by num	Ensure the algorithm correctly handles carry-overs that propagate beyond the most significant digit and extend the array if necessary.
Input array num contains only a single '0'	Adding to this should not result in leading zeros.
Large array size for num (performance consideration)	Use an efficient algorithm that avoids unnecessary memory allocation or copying to maintain acceptable performance for large arrays.
k is a single digit number and the last element in array num + k is more than 9	Ensure carry is handled correctly when only the last digit changes when k is added.

Empty input array num

How to Handle:

Treat an empty input array as the integer 0 and proceed with the addition with k.

k is zero

How to Handle:

Return the original array num if k is zero, as no addition is needed.

Large value of k that results in integer overflow in intermediate calculations

How to Handle:

Perform digit-by-digit addition and carry-over to avoid exceeding integer limits.

The input array num contains leading zeros

How to Handle:

Remove the leading zeros from the array at the beginning or during the processing.

The sum has more digits than either k or the number represented by num

How to Handle:

Ensure the algorithm correctly handles carry-overs that propagate beyond the most significant digit and extend the array if necessary.

Input array num contains only a single '0'

How to Handle:

Adding to this should not result in leading zeros.

Large array size for num (performance consideration)

How to Handle:

Use an efficient algorithm that avoids unnecessary memory allocation or copying to maintain acceptable performance for large arrays.

k is a single digit number and the last element in array num + k is more than 9

How to Handle:

Ensure carry is handled correctly when only the last digit changes when k is added.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the `num` array and the value of `k`? Can `k` be negative?
Can the elements in the `num` array be negative?
If the sum results in a leading zero, should I remove it from the result?
Is the input array `num` guaranteed to be a valid array representation of a non-negative integer (e.g., no leading zeros unless the number is zero itself)?
Could `num` be an empty array?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the digit list and combine all the digits to form one single large number.
Add the other given number to this large number to get their sum.
Break down the sum back into individual digits and create a new list of these digits. This list represents the array-form of the resulting sum.

Code Implementation

def add_to_array_form_of_integer(digit_list, number_to_add):
    # Convert the digit list into a single large number
    large_number = 0
    for digit in digit_list:
        large_number = large_number * 10 + digit

    # Add the other given number to this large number
    sum_of_numbers = large_number + number_to_add

    # Convert the sum back into a list of digits
    result_list = []
    if sum_of_numbers == 0:
        result_list.append(0)
    else:
        while sum_of_numbers > 0:
            # Extract the last digit
            digit = sum_of_numbers % 10

            result_list.append(digit)

            # Remove the last digit
            sum_of_numbers //= 10

    # Reverse the list to get the correct order
    result_list.reverse()
    return result_list

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the rightmost digit of the array and the rightmost digit of the number K.
Add these two digits together.
If the sum is 10 or more, keep the rightmost digit as part of the result and carry-over the '1' to the next column (just like in grade school addition).
Move to the next digit in the array (going from right to left) and the next digit of K (if K has more digits).
Repeat the addition and carry-over process.
If you run out of digits in the array but K still has digits, keep adding the digits of K along with any carry-over values.
If you run out of digits in K but the array still has digits, keep adding the digits of the array along with any carry-over values.
If there's a final carry-over value after processing all digits, add it to the beginning of the result.
The result is a new array representing the sum of the original array and the number K.

Code Implementation

def addToArrayForm(number_array, k_value):
    result_array = []
    array_length = len(number_array) - 1
    carry_over = 0

    while array_length >= 0 or k_value > 0:
        current_sum = carry_over

        if array_length >= 0:
            current_sum += number_array[array_length]
            array_length -= 1

        if k_value > 0:
            current_sum += k_value % 10
            k_value //= 10

        # If sum >= 10, we extract the digit and propagate carry.
        result_array.append(current_sum % 10)
        carry_over = current_sum // 10

    # Add any final carry to the result.
    if carry_over > 0:
        result_array.append(carry_over)

    result_array.reverse()
    return result_array

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array num	Treat an empty input array as the integer 0 and proceed with the addition with k.
k is zero	Return the original array num if k is zero, as no addition is needed.
Large value of k that results in integer overflow in intermediate calculations	Perform digit-by-digit addition and carry-over to avoid exceeding integer limits.
The input array num contains leading zeros	Remove the leading zeros from the array at the beginning or during the processing.
The sum has more digits than either k or the number represented by num	Ensure the algorithm correctly handles carry-overs that propagate beyond the most significant digit and extend the array if necessary.
Input array num contains only a single '0'	Adding to this should not result in leading zeros.
Large array size for num (performance consideration)	Use an efficient algorithm that avoids unnecessary memory allocation or copying to maintain acceptable performance for large arrays.
k is a single digit number and the last element in array num + k is more than 9	Ensure carry is handled correctly when only the last digit changes when k is added.

Empty input array num

How to Handle:

Treat an empty input array as the integer 0 and proceed with the addition with k.

k is zero

How to Handle:

Return the original array num if k is zero, as no addition is needed.

Large value of k that results in integer overflow in intermediate calculations

How to Handle:

Perform digit-by-digit addition and carry-over to avoid exceeding integer limits.

The input array num contains leading zeros

How to Handle:

Remove the leading zeros from the array at the beginning or during the processing.

The sum has more digits than either k or the number represented by num

How to Handle:

Ensure the algorithm correctly handles carry-overs that propagate beyond the most significant digit and extend the array if necessary.

Input array num contains only a single '0'

How to Handle:

Adding to this should not result in leading zeros.

Large array size for num (performance consideration)

How to Handle:

Use an efficient algorithm that avoids unnecessary memory allocation or copying to maintain acceptable performance for large arrays.

k is a single digit number and the last element in array num + k is more than 9

How to Handle:

Ensure carry is handled correctly when only the last digit changes when k is added.

0/1114 Microsoft questions completed

0/1114 completed