1. Problem Statement (Simple Explanation):
You’re given two non-negative integers num1 and num2 as strings.
You must:
Return their product as a string.
You cannot:
Use built-in big integer libraries.
Convert the entire strings directly to integers.
Lengths:
1 <= len(num1), len(num2) <= 200
Digits only, no leading zero except "0" itself.
2. Examples:
Example 1:
Input: num1 = "2", num2 = "3"
2 * 3 = 6
Output: "6"
Example 2:
Input: num1 = "123", num2 = "456"
123 * 456 = 56088
Output: "56088"
3. Intuition – Simulate Grade-School Multiplication:
We multiply like on paper:
For num1 = "123", num2 = "456":
1 2 3
x 4 5 6
---------
7 3 8 (123 * 6, shifted by 0)
6 1 5 (123 * 5, shifted by 1)
4 9 2 (123 * 4, shifted by 2)
---------
5 6 0 8 8
But instead of summing separate rows, we can directly use indexing into an array of size m + n, where m = len(num1), n = len(num2).
Indexing Trick:
Let:
i index in num1 from right to left (least significant digit).
j index in num2 from right to left.
If:
num1[i] contributes a = digit(num1[i])
num2[j] contributes b = digit(num2[j])
Then:
The product a * b contributes to positions:
p1 = i + j
p2 = i + j + 1
in a result array of length m + n.
We accumulate multiplication and carry:
sum = a*b + result[p2]
result[p2] = sum % 10
result[p1] += sum / 10
At the end, result holds digits (possibly with leading zeros), and we build the string skipping leading zeros.
4. Algorithm (Step-by-Step):
If either num1 == "0" or num2 == "0", return "0".
Let:
m = len(num1)
n = len(num2)
result = int array of size m + n, initialized to 0
Loop over digits from right to left:
for i from m-1 down to 0:
for j from n-1 down to 0:
a = num1[i] - '0'
b = num2[j] - '0'
mul = a * b
p1 = i + j
p2 = i + j + 1
sum = mul + result[p2]
result[p2] = sum % 10
result[p1] += sum / 10
Convert result array to string:
Skip leading zeros.
Append digits to a builder.
If after skipping zeros, the string is empty → return "0", otherwise return the built string.
Pseudo-code:
Complexity:
Let:
M = |num1|, n = |num2|
Then:
Time: O(m*n) – nested loops.
Space: O(m + n) for the result array.
Given m, n <= 200, this is efficient.
5. Java code:
6. C code:
7. C++ code:
9. JavaScript code:
Comments
Post a Comment