Jobs

Interviews

Discussions

Multiply Strings

Medium

Google

2 views

Topics:

StringsArrays

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

For example:

num1 = "2", num2 = "3" should return "6"
num1 = "123", num2 = "456" should return "56088"

Constraints:

1 <= num1.length, num2.length <= 200
num1 and num2 consist of digits only.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.

Could you provide an algorithm to solve this problem, considering the constraints?

Multiply Strings

Medium

Google

2 views

Topics:

StringsArrays

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

For example:

num1 = "2", num2 = "3" should return "6"
num1 = "123", num2 = "456" should return "56088"

Constraints:

1 <= num1.length, num2.length <= 200
num1 and num2 consist of digits only.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.

Could you provide an algorithm to solve this problem, considering the constraints?

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:

Can the input strings contain leading zeros, and should the output string also avoid leading zeros?
Are the input strings guaranteed to contain only digits, or should I handle non-digit characters?
What is the maximum possible length of the input strings? Is there a limit to the size of the resulting product?
Can either of the input strings be an empty string or null?
Should I return an error or a specific value (e.g., "0") if either of the input strings is "0"?

Brute Force Solution

Approach

We're given two numbers represented as strings, and we want to find their product, also as a string. The brute force approach mimics how you would do multiplication by hand on paper, multiplying each digit of one number with each digit of the other number and then handling the carries.

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

Take the first digit of the second number and multiply it by the first number, treating them as regular numbers.
Write down the result of that multiplication.
Next, take the second digit of the second number and multiply it by the first number.
Write down this result, but shift it one place to the left, just like you do when multiplying by hand.
Repeat this process for all the digits in the second number, shifting the result one more place to the left each time.
Finally, add up all the shifted results you wrote down. This gives you the final product, which you then represent as a string.

Code Implementation

def multiply_strings_brute_force(first_number, second_number):
    intermediate_results = []

    for second_index in range(len(second_number) - 1, -1, -1):
        carry = 0
        current_result = []
        second_digit = int(second_number[second_index])

        for first_index in range(len(first_number) - 1, -1, -1):
            first_digit = int(first_number[first_index])
            product = first_digit * second_digit + carry
            current_result.append(product % 10)
            carry = product // 10

        if carry:
            current_result.append(carry)

        current_result.reverse()
        intermediate_results.append(current_result)

    final_result = [0]

    # Simulate addition with carry
    for i, result in enumerate(intermediate_results):
        shift = len(intermediate_results) - 1 - i
        padded_result = result + [0] * shift
        len_diff = len(final_result) - len(padded_result)

        if len_diff < 0:

            final_result = [0] * abs(len_diff) + final_result

        elif len_diff > 0:

            padded_result = [0] * len_diff + padded_result

        carry = 0
        temp_sum = []

        for j in range(len(final_result) - 1, -1, -1):
            digit_sum = final_result[j] + padded_result[j] + carry
            temp_sum.append(digit_sum % 10)
            carry = digit_sum // 10

        if carry:
            temp_sum.append(carry)

        temp_sum.reverse()
        final_result = temp_sum

    # Remove leading zeros
    while len(final_result) > 1 and final_result[0] == 0:
        final_result.pop(0)

    return ''.join(map(str, final_result))

Big(O) Analysis

Time Complexity

O(m*n) – Let 'm' be the length of the first number and 'n' be the length of the second number. The core operation involves multiplying each digit of the second number ('n' digits) with the first number ('m' digits). This results in 'n' multiplications, each taking O(m) time. We also need to add these intermediate products. Adding two numbers of length at most m+n takes O(m+n) which we approximate by O(m+n). We perform additions 'n' times so we can have a total of n*O(m+n). Combining all these costs, multiplication is O(m*n) and adding the resulting strings is n * O(m+n), which are dominated by the multiplication so we are left with a complexity of O(m*n).

Space Complexity

O(m*n) – The algorithm involves multiplying each digit of the first number (length m) with each digit of the second number (length n). This creates m intermediate results each having at most m+n digits. The shifted results from these multiplications are stored before being added. Therefore, the auxiliary space scales linearly with the product of the lengths of the input strings, resulting in O(m*n) space complexity, where m and n represent the lengths of the two input strings.

Optimal Solution

Approach

The trick to multiplying large numbers represented as strings is to simulate how you'd do it by hand, but work with individual digits instead of the whole numbers. We'll multiply each digit of one number by each digit of the other, and then carefully add up the intermediate results, handling carries along the way.

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

Imagine you're multiplying the numbers on paper. First, you'll multiply one digit of the second number by all the digits of the first number.
Write down this result, properly aligned based on which digit of the second number you used. For example, if multiplying by the 'tens' digit, shift your result one place to the left (add a zero).
Repeat this process for each digit of the second number, creating a series of partial products that are each shifted appropriately.
Now, add up all the partial products to get the final result. Just like in regular addition, handle carries when the sum of digits in a column exceeds ten.
Because we're working with digits extracted from strings, remember to convert them to numbers for multiplication and back to strings when storing or adding the results.
Finally, remove any leading zeros from the result string to have a clean answer.

Code Implementation

def multiply_strings(number1, number2):
    if number1 == "0" or number2 == "0":
        return "0"

    length_of_number1 = len(number1)
    length_of_number2 = len(number2)

    # This will store the intermediate products.
    intermediate_products = [0] * (length_of_number1 + length_of_number2)

    for i in range(length_of_number1 - 1, -1, -1):
        for j in range(length_of_number2 - 1, -1, -1):
            digit_number1 = int(number1[i])
            digit_number2 = int(number2[j])

            product = digit_number1 * digit_number2

            # Determine positions in the result array.
            position1 = i + j
            position2 = i + j + 1

            sum_at_position2 = intermediate_products[position2] + product

            # Add the new product, propagating carry.
            intermediate_products[position2] = sum_at_position2 % 10

            intermediate_products[position1] += sum_at_position2 // 10

    result = "".join(map(str, intermediate_products))

    # Remove leading zeros from the result
    start = 0
    while start < len(result) - 1 and result[start] == '0':
        start += 1

    # Ensure no leading zeros
    return result[start:]

Big(O) Analysis

Time Complexity

O(m*n) – The dominant operation is the multiplication of each digit in num2 (of length m) by each digit in num1 (of length n). This results in m * n individual multiplications. The addition of the partial products then requires iterating at most m+n times. Since m*n grows faster than m+n, the overall time complexity is O(m*n).

Space Complexity

O(m+n) – The space complexity is primarily determined by the size of the `products` array which stores intermediate results. In the worst case, multiplying an m-digit number by an n-digit number can result in an intermediate product of length m+n. The final result string also has a maximum length of m+n. Therefore, the auxiliary space used is proportional to m+n, where m and n are the lengths of the two input strings.

Edge Cases

Case	How to Handle
One or both input strings are null or empty	Return '0' if either input is null or empty as multiplying by zero results in zero.
One or both input strings are '0'	Return '0' immediately if either input is '0' to avoid unnecessary calculations.
Input strings contain leading zeros (e.g., '00123')	Trim leading zeros from the input strings before performing the multiplication to avoid incorrect results.
Very large input strings that could lead to integer overflow	Use an array to store intermediate multiplication results, simulating manual multiplication, to handle large numbers.
Input strings containing non-digit characters	Throw an exception or return an error message indicating invalid input if non-digit characters are encountered.
Input strings represent negative numbers	Handle sign by checking the sign of both numbers, multiplying absolute values and applying correct sign to the final result.
Maximum length input strings allowed by memory constraints	Ensure that the allocated memory for the result array is sufficient to hold the product of the two largest possible numbers.
Both input strings are '1'	The algorithm should correctly return '1' as the product of 1 and 1 is 1 without errors.

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:

Can the input strings contain leading zeros, and should the output string also avoid leading zeros?
Are the input strings guaranteed to contain only digits, or should I handle non-digit characters?
What is the maximum possible length of the input strings? Is there a limit to the size of the resulting product?
Can either of the input strings be an empty string or null?
Should I return an error or a specific value (e.g., "0") if either of the input strings is "0"?

Brute Force Solution

Approach

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

Take the first digit of the second number and multiply it by the first number, treating them as regular numbers.
Write down the result of that multiplication.
Next, take the second digit of the second number and multiply it by the first number.
Write down this result, but shift it one place to the left, just like you do when multiplying by hand.
Repeat this process for all the digits in the second number, shifting the result one more place to the left each time.
Finally, add up all the shifted results you wrote down. This gives you the final product, which you then represent as a string.

Code Implementation

def multiply_strings_brute_force(first_number, second_number):
    intermediate_results = []

    for second_index in range(len(second_number) - 1, -1, -1):
        carry = 0
        current_result = []
        second_digit = int(second_number[second_index])

        for first_index in range(len(first_number) - 1, -1, -1):
            first_digit = int(first_number[first_index])
            product = first_digit * second_digit + carry
            current_result.append(product % 10)
            carry = product // 10

        if carry:
            current_result.append(carry)

        current_result.reverse()
        intermediate_results.append(current_result)

    final_result = [0]

    # Simulate addition with carry
    for i, result in enumerate(intermediate_results):
        shift = len(intermediate_results) - 1 - i
        padded_result = result + [0] * shift
        len_diff = len(final_result) - len(padded_result)

        if len_diff < 0:

            final_result = [0] * abs(len_diff) + final_result

        elif len_diff > 0:

            padded_result = [0] * len_diff + padded_result

        carry = 0
        temp_sum = []

        for j in range(len(final_result) - 1, -1, -1):
            digit_sum = final_result[j] + padded_result[j] + carry
            temp_sum.append(digit_sum % 10)
            carry = digit_sum // 10

        if carry:
            temp_sum.append(carry)

        temp_sum.reverse()
        final_result = temp_sum

    # Remove leading zeros
    while len(final_result) > 1 and final_result[0] == 0:
        final_result.pop(0)

    return ''.join(map(str, final_result))

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you're multiplying the numbers on paper. First, you'll multiply one digit of the second number by all the digits of the first number.
Write down this result, properly aligned based on which digit of the second number you used. For example, if multiplying by the 'tens' digit, shift your result one place to the left (add a zero).
Repeat this process for each digit of the second number, creating a series of partial products that are each shifted appropriately.
Now, add up all the partial products to get the final result. Just like in regular addition, handle carries when the sum of digits in a column exceeds ten.
Because we're working with digits extracted from strings, remember to convert them to numbers for multiplication and back to strings when storing or adding the results.
Finally, remove any leading zeros from the result string to have a clean answer.

Code Implementation

def multiply_strings(number1, number2):
    if number1 == "0" or number2 == "0":
        return "0"

    length_of_number1 = len(number1)
    length_of_number2 = len(number2)

    # This will store the intermediate products.
    intermediate_products = [0] * (length_of_number1 + length_of_number2)

    for i in range(length_of_number1 - 1, -1, -1):
        for j in range(length_of_number2 - 1, -1, -1):
            digit_number1 = int(number1[i])
            digit_number2 = int(number2[j])

            product = digit_number1 * digit_number2

            # Determine positions in the result array.
            position1 = i + j
            position2 = i + j + 1

            sum_at_position2 = intermediate_products[position2] + product

            # Add the new product, propagating carry.
            intermediate_products[position2] = sum_at_position2 % 10

            intermediate_products[position1] += sum_at_position2 // 10

    result = "".join(map(str, intermediate_products))

    # Remove leading zeros from the result
    start = 0
    while start < len(result) - 1 and result[start] == '0':
        start += 1

    # Ensure no leading zeros
    return result[start:]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
One or both input strings are null or empty	Return '0' if either input is null or empty as multiplying by zero results in zero.
One or both input strings are '0'	Return '0' immediately if either input is '0' to avoid unnecessary calculations.
Input strings contain leading zeros (e.g., '00123')	Trim leading zeros from the input strings before performing the multiplication to avoid incorrect results.
Very large input strings that could lead to integer overflow	Use an array to store intermediate multiplication results, simulating manual multiplication, to handle large numbers.
Input strings containing non-digit characters	Throw an exception or return an error message indicating invalid input if non-digit characters are encountered.
Input strings represent negative numbers	Handle sign by checking the sign of both numbers, multiplying absolute values and applying correct sign to the final result.
Maximum length input strings allowed by memory constraints	Ensure that the allocated memory for the result array is sufficient to hold the product of the two largest possible numbers.
Both input strings are '1'	The algorithm should correctly return '1' as the product of 1 and 1 is 1 without errors.