algoadvance

The problem requires you to multiply two non-negative integers represented as strings and return the product, also as a string. You should not use any built-in libraries for large integers such as Python’s int or decimal. The input strings consist of numeric characters only and do not contain any leading zeros, except when the input string is “0”.

Clarifying Questions

  1. Size Limits: Is there a constraint on the size of the input strings?
    • Response: Typical constraints can involve up to a few thousand digits.
  2. Input Validation: Do we need to handle invalid inputs, such as non-numeric characters?
    • Response: No, we may assume inputs are always valid.
  3. Leading Zeros: How should we handle leading zeros in the result?
    • Response: The result string should not have leading zeros unless the result itself is “0”.

Strategy

To simulate the multiplication of two large integers represented as strings, we can employ a technique that mimics the manual multiplication taught in elementary school:

  1. Initialization:
    • Treat each digit in the input strings individually.
    • Use an array to store the intermediate results of the multiplication.
  2. Multiplication:
    • Multiply each digit of the first number by each digit of the second number.
    • Store the results in the correct position in the result array, taking into account the offset due to the positions of the digits.
  3. Handling Carry:
    • If a position in the result array exceeds 9 (i.e., it has a carry), propagate this carry to the next position.
  4. Convert to String:
    • Convert the result array back into a string, skipping any leading zeros in the process.
  5. Edge Case:
    • If both inputs are “0”, return “0”.

Code

def multiply(num1: str, num2: str) -> str:
    if num1 == "0" or num2 == "0":
        return "0"
    
    len1, len2 = len(num1), len(num2)
    # Result can be at most len1 + len2 digits
    result = [0] * (len1 + len2)
    
    # Reverse both strings to simplify position handling
    num1, num2 = num1[::-1], num2[::-1]
    
    # Multiply each digit and add to result
    for i in range(len1):
        for j in range(len2):
            digit_mul = int(num1[i]) * int(num2[j])
            result[i + j] += digit_mul
            # Handle carry over to the next position
            result[i + j + 1] += result[i + j] // 10
            result[i + j] %= 10
    
    # Convert result to string and remove leading zeros
    while len(result) > 1 and result[-1] == 0:
        result.pop()
    
    return ''.join(map(str, result[::-1]))

# Example usage
num1 = "123"
num2 = "456"
print(multiply(num1, num2))  # Output: "56088"

Time Complexity

Try our interview co-pilot at AlgoAdvance.com