Multiply two huge numbers stored as strings, like on paper: each digit pair lands at position i + j + 1, then carry the overflow leftward.
▼The problem
LeetCode 43 (Medium). Given two non-negative integers num1 and num2 as strings, return their product, also as a string, without converting the inputs to integers directly and without a big-integer library. Up to 200 digits each, no leading zeros except the number 0 itself.
Examples: "2" × "3" → "6" and "123" × "456" → "56088" (LeetCode's); "0" × "52" → "0" (the slots read "000"; the answer is a single zero).
The solution
def multiply(num1, num2):
m, n = len(num1), len(num2)
pos = [0] * (m + n) # m + n slots
for i in range(m - 1, -1, -1): # from the right
for j in range(n - 1, -1, -1):
mul = int(num1[i]) * int(num2[j])
total = mul + pos[i + j + 1]
pos[i + j + 1] = total % 10 # keep
pos[i + j] += total // 10 # carry
out = ''.join(map(str, pos)).lstrip('0')
return out or '0'Transcript
Multiply Strings. Two numbers come as strings of digits. Return their product, also as a string. No converting to integers, and no big number library.
Two times three is six. One twenty-three times four fifty-six is fifty-six thousand and eighty-eight. Zero times fifty-two is just zero, with no leading zeros.
The obvious way: convert to numbers, multiply, convert back. That breaks the rules, and two hundred digits overflow any normal integer.
The key idea: multiply like in school, digit by digit. The answer fits in m plus n digits: make that many slots. Digit i times digit j always lands in slot i plus j plus one, and its carry goes to slot i plus j. It's carrying again, like Plus One, now with products.
In code, loop over both strings from the right. Add each product to slot i plus j plus one. Keep its last digit there; carry the tens into slot i plus j. Finally, skip leading zeros and join.
One twenty-three times four fifty-six. Three times six is eighteen: keep eight, carry one. Three times five is fifteen, plus one, sixteen. Three times four is twelve, plus one, thirteen. The two row, one slot left: twelve, ten, eight. The one row: six, five, four. The slots read zero, five, six, zero, eight, eight. Skip the zero: fifty-six thousand and eighty-eight.
Every digit pair meets once: m times n time. The slots take m plus n space.
Multiply each digit pair, drop it in slot i plus j plus one, carry left. That's Multiply Strings.