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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Multiply Strings

Difficulty: Medium

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

  • The product of two numbers can be computed using the traditional multiplication method (like how we do it by hand).
  • We need to handle the multiplication digit by digit and account for carries.
  • The result can be stored in an array where each index represents a position in the final product string.
  • We need to convert the final result from the array into a string format before returning it.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of num1 and m is the length of num2.
Space Complexity: O(n + m), for storing the intermediate results in an array.

Solution

To solve this problem, we can use an array to hold the intermediate results of the multiplication. We will iterate through each digit of num1 and num2, multiply them together, and add the results to the appropriate index in the result array, taking care to handle carries. Finally, we will convert the result array into a string format and return it.

Code Solutions

def multiply(num1: str, num2: str) -> str:
    if num1 == "0" or num2 == "0":
        return "0"
    
    # Initialize an array to hold the result
    result = [0] * (len(num1) + len(num2))
    
    # Reverse iterate through both strings
    for i in range(len(num1) - 1, -1, -1):
        for j in range(len(num2) - 1, -1, -1):
            # Multiply the digits and add to the corresponding position
            mul = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
            p1, p2 = i + j, i + j + 1
            # Add to the result and manage carry
            total = mul + result[p2]
            result[p2] = total % 10
            result[p1] += total // 10
    
    # Convert result array to string
    result_str = ''.join(map(str, result))
    return result_str.lstrip('0')
← Back to All Questions