Algorithm Steps
-
Iterate the array in reverse order
- Convert each character of
num1 and num2 to integer, and store conversion results in integer array A and B
-
Simulate multiplication
- When multiplying 2 numbers of length
n and m, the result has at most n + m digits
- Multiply A and B bit by bit accumulation，and store result in array
C
-
Handle carries
- Each digit of
C is treated as unit digit, and the carry-over is accumulated to the next digit
-
Remove leading 0 and generate the result string
- Search for the first non-zero bit in the
C from higher bit to the lower bit
- Convert the result array to string
Complexity Analysis
- Length of
num1 and num2 is n and m
- Simulate multiplication
O(n * m)
- Handel carries and generate result string
O(n + m)
Overall time complexity O(n * m)
Length of Result array C is n + m，space complexity O(n + m)
C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
class Solution {
public:
string multiply(string num1, string num2)
{
// get the length of num1 and num2
int n = num1.size(), m = num2.size();
// iterate the string in reverse order and convert to integer array
std::vector<int> A, B;
for (int i = n - 1; i >= 0; --i)
A.push_back(num1[i] - '0');
for (int i = m - 1; i >= 0; --i)
B.push_back(num2[i] - '0');
// initialize result array C
std::vector<int> C(n + m, 0);
// simulate multiplication
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
C[i + j] += A[i] * B[j];
// handle carries
for (int i = 0, t = 0; i < C.size(); ++i)
{
t += C[i];
C[i] = t % 10; // keep unit digit
t /= 10; // process carry part
}
// remove leading zeros
int k = C.size() - 1;
while (k > 0 && C[k] == 0) --k;
// convert integer array to string
std::string res;
while (k >= 0)
res += C[k--] + '0';
return res;
}
};
|
Python Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution:
def multiply(self, num1: str, num2: str) -> str:
n, m = len(num1), len(num2)
A = [int(num1[i]) for i in range(n - 1, -1, -1)]
B = [int(num2[i]) for i in range(m - 1, -1, -1)]
C = [0] * (n + m)
for i in range(n):
for j in range(m):
C[i + j] += A[i] * B[j]
t = 0
for i in range(len(C)):
t += C[i]
C[i] = t % 10
t //= 10
k = len(C) - 1
while k > 0 and C[k] == 0:
k -= 1
res = ""
while k >= 0:
res += str(C[k])
k -= 1
return res
|
Go Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
func multiply(num1 string, num2 string) string {
n, m := len(num1), len(num2)
A := make([]int, n)
B := make([]int, m)
for i := 0; i < n; i ++ {
A[i] = int(num1[n - 1 - i] - '0')
}
for i := 0; i < m; i ++ {
B[i] = int(num2[m - 1 - i] - '0')
}
C := make([]int, n + m)
for i := range A {
for j := range B {
C[i + j] += A[i] * B[j]
}
}
t := 0
for i := 0; i < len(C); i ++ {
t += C[i]
C[i] = t % 10
t /= 10
}
k := len(C) - 1
for k > 0 && C[k] == 0 {
k -= 1
}
res := ""
for k >= 0 {
res += string(C[k] + '0')
k -= 1
}
return res
}
|
JavaScript Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
var multiply = function (num1, num2) {
let n = num1.length,
m = num2.length;
let A = [],
B = [];
for (let i = n - 1; i >= 0; i--) {
A.push(Number(num1[i]));
}
for (let i = m - 1; i >= 0; i--) {
B.push(Number(num2[i]));
}
let C = new Array(n + m).fill(0);
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
C[i + j] += A[i] * B[j];
}
}
let t = 0;
for (let i = 0; i < C.length; i++) {
t += C[i];
C[i] = t % 10;
t = Math.trunc(t / 10);
}
let k = C.length - 1;
while (k > 0 && C[k] === 0) {
k--;
}
let res = "";
while (k >= 0) {
res += String(C[k--]);
}
return res;
};
|
