The problem
Given two non-negative integers as strings of digits, return their product, also as a string — without converting them to numbers, which could be too large.
Examples
01
- Input
num1 = "2", num2 = "3"
- Output
"6"
02
- Input
num1 = "123", num2 = "456"
- Output
"56088"
Constraints
- 1 ≤ num1.length, num2.length ≤ 200
- Digits only, no leading zeros except the number 0 itself.
The idea
Long multiplication, as on paper. The product of an m-digit and an n-digit number has at most m + n digits, so make that many places. Counting from the left, digit i of num1 times digit j of num2 contributes to place i + j + 1.
Go from the right. Add each digit product into its place, keep the last digit there, and push the carry one place left. At the end, drop leading zeros. For 123 × 456 this gives 56088.
- Time
- O(m · n)
- Space
- O(m + n)
Solution · every language run against every case
class Solution: def multiply(self, num1: str, num2: str) -> str: if num1 == "0" or num2 == "0": return "0" # Long multiplication: digit i of num1 times digit j of num2 lands at place i + j + 1 # of the product (counting from the left, with room for one extra digit). out = [0] * (len(num1) + len(num2)) for i in range(len(num1) - 1, -1, -1): for j in range(len(num2) - 1, -1, -1): total = out[i + j + 1] + int(num1[i]) * int(num2[j]) out[i + j + 1] = total % 10 out[i + j] += total // 10 # the carry, settled when that place is reached return "".join(map(str, out)).lstrip("0")