We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Multiply Strings

Number: 43

Difficulty: Medium

Paid? No

Companies: Meta, Google, Zoho, Microsoft, Amazon, Two Sigma, Bloomberg, Apple, Pinterest, TikTok, X

Problem Description

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. You must not use any built-in BigInteger library or convert the inputs to integer directly.

Key Insights

  • Simulate the multiplication process similar to hand multiplication.
  • Use an array to store intermediate results where the index correlation is based on the position of digits.
  • Each multiplication may contribute a value that needs to be managed with a carry over in the result array.
  • Handle the special case when either input is "0".

Space and Time Complexity

Time Complexity: O(n * m), where n and m are the lengths of num1 and num2 respectively.
Space Complexity: O(n + m), used for storing the intermediate multiplication results.

Solution

The solution multiplies each digit of num1 with each digit of num2 by simulating the grade-school multiplication algorithm. An array is used to store the intermediate sums at positions that correspond to the sum of the indices from num1 and num2. For two digits multiplied together, the product is added to the corresponding index in the result array, and any carry is added to the adjacent left cell. Finally, the array is converted back to a string while taking care to remove any leading zeros.

Data structures used:

  • Array for intermediate multiplication results.
  • Two nested loops to multiply each digit pair.

Algorithmic steps:

  1. Initialize an array of size (length of num1 + length of num2) with all zeros.
  2. Loop through digits of num1 and num2 in reverse order.
  3. Multiply the two digits, add the product to the corresponding position in the result array (taking into account any previous values).
  4. Manage the carry for each index.
  5. Convert the result array to a string, skipping any leading zeros.
  6. Return the final product string.

Code Solutions

# Python implementation with line-by-line comments

def multiply(num1, num2):
    # If either string is "0", the product is "0".
    if num1 == "0" or num2 == "0":
        return "0"
    
    n, m = len(num1), len(num2)
    # Initialize an array to store the product results.
    result = [0] * (n + m)
    
    # Multiply each digit of num1 with each digit of num2.
    for i in range(n - 1, -1, -1):
        for j in range(m - 1, -1, -1):
            # Multiply current digits.
            product = int(num1[i]) * int(num2[j])
            # Position in the result array where the product should be added.
            pos = i + j + 1
            total = product + result[pos]
            result[pos] = total % 10  # Place the digit at the current index.
            result[pos - 1] += total // 10  # Carry over the remaining value.
    
    # Convert the result array into a string, skipping any leading zero.
    result_str = ''.join(map(str, result)).lstrip('0')
    return result_str if result_str else "0"

# Example usage:
print(multiply("123", "456"))  # Expected output: "56088"
← Back to All Questions