Description
Multiply two nonnegative integers written as decimal strings. Return the product as a decimal string without leading zeros. Do not convert either whole input to an integer.
Solution
def multiply(num1, num2):
digits = [0] * (len(num1) + len(num2))
for i in range(len(num1)):
for j in range(len(num2)):
digits[i + j + 1] += (ord(num1[i]) - 48) * (ord(num2[j]) - 48)
for i in range(len(digits) - 1, 0, -1):
digits[i - 1] += digits[i] // 10
digits[i] %= 10
start = 0
while start < len(digits) - 1 and digits[start] == 0:
start += 1
return "".join(str(value) for value in digits[start:])Examples
Example 1
- Input
["2","3"]- Output
"6"
One digit pair multiplies directly.
Example 2
- Input
["123","456"]- Output
"56088"
The product has five digits.
Example 3
- Input
["0","999"]- Output
"0"
Any factor zero makes the product zero.
Approach
Accumulate each digit pair's product into an array of length m + n. Normalize carries from right to left, remove leading zeros, and join the remaining digits.
Time & space
O(mn) time and O(m + n) auxiliary space, where m and n are input digit counts.