Example 1
ready- Input
num1 = "2" num2 = "3"- Expected
"6"- Why
- one digit pair produces the whole product
Multiply Strings
35 min · multiply()mediumOpen in LeetCode #43 ↗
Two account totals arrive as text because each one may be hundreds of digits long. You need to multiply the digits themselves, not hand the strings to a huge-number parser.
Given two strings num1 and num2 representing non-negative integers, return their
product as a decimal string.
Use grade-school multiplication—multiplying digit pairs and carrying place values, as you would on paper. Don't convert either full input to a built-in big-integer type, a type that grows to store integers beyond an ordinary machine integer's range.
A few ground rules:
- Every character in each input is a decimal digit.
- Inputs have no leading zeros unless the whole input is
"0". - If either factor is
"0", return"0". - A product of lengths
mandnneeds at mostm + ndigit slots.
Constraints
1 <= num1.length, num2.length <= 200num1andnum2contain decimal digits only.- Neither input has a leading zero unless it is exactly
"0".
Hints
Reserve every possible place
Create an array of num1.length + num2.length zeros. A digit from index i times
a digit from index j contributes around positions i + j and i + j + 1.
Accumulate before carrying
Add every digit-pair product into slot i + j + 1. Then walk the result from right
to left, leaving value % 10 and carrying value // 10 one slot left.
Normalize the answer
Skip zero slots at the front after all carries are settled. Keep one zero only for the actual zero product.
Follow-up
Can you explain why m + n slots are always enough, even when every digit creates a carry?
Visible cases
Examples
Example 2
ready- Input
num1 = "123" num2 = "456"- Expected
"56088"- Why
- the digit-pair products combine through carries
Example 3
ready- Input
num1 = "0" num2 = "52"- Expected
"0"- Why
- a zero factor makes the product zero
Interview signal
Asked at
AmazonGoogleMeta
Partial products + addition
Mirror the full paper calculation. Multiply the longer input by one digit of the shorter input, append zeros for that digit's place, then add the row into a running decimal-string total. Neither helper ever converts the full number to an integer.
def add_decimal(left: str, right: str) -> str:
i, j = len(left) - 1, len(right) - 1
carry = 0
out: list[str] = []
while i >= 0 or j >= 0 or carry:
a = ord(left[i]) - ord("0") if i >= 0 else 0
b = ord(right[j]) - ord("0") if j >= 0 else 0
total = a + b + carry
out.append(str(total % 10))
carry = total // 10
i -= 1
j -= 1
return "".join(reversed(out))
def multiply_by_digit(num: str, digit: int, zeros: int) -> str:
if digit == 0:
return "0"
carry = 0
out: list[str] = []
for char in reversed(num):
total = (ord(char) - ord("0")) * digit + carry
out.append(str(total % 10))
carry = total // 10
if carry:
out.append(str(carry))
return "".join(reversed(out)) + "0" * zeros
def multiply(num1: str, num2: str) -> str:
if num1 == "0" or num2 == "0":
return "0"
if len(num1) < len(num2):
num1, num2 = num2, num1
total = "0"
for place, char in enumerate(reversed(num2)):
row = multiply_by_digit(num1, ord(char) - ord("0"), place)
total = add_decimal(total, row)
return totalChoosing the shorter string for the row count keeps the total character work bounded by the number of digit pairs.
Time O(mn) across the partial rows and additions. Space O(m + n) for the current row, running total, and output buffers.
One digit accumulator
The partial rows can share one array. Multiplying digits at indices i and j
contributes to slot i + j + 1. Accumulate every raw product there, then make one
right-to-left pass that pushes each carry into the slot on its left.
def multiply(num1: str, num2: str) -> str:
if num1 == "0" or num2 == "0":
return "0"
m, n = len(num1), len(num2)
digits = [0] * (m + n)
for i in range(m - 1, -1, -1):
first = ord(num1[i]) - ord("0")
for j in range(n - 1, -1, -1):
second = ord(num2[j]) - ord("0")
digits[i + j + 1] += first * second
for k in range(m + n - 1, 0, -1):
digits[k - 1] += digits[k] // 10
digits[k] %= 10
start = 0
while start < len(digits) - 1 and digits[start] == 0:
start += 1
return "".join(str(digit) for digit in digits[start:])The largest product of an m-digit and an n-digit number has m + n digits, so the
array can't run out of room. Removing leading zero slots produces the normalized string.
Time O(mn) for every digit pair. Space O(m + n) for the accumulator and returned string.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
"6"
Run: visible + custom · Submit: full suite