Problem
Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.
Actually, this is the multiplication of unsigned integers represented by strings.
Algorithm
O(n^2)
Single digits multiplication does not overflow.
Divide-and-Conquer
Assume a and b has the same length, we can use a divide and conquer technique to reduce the running time.
a*b = (aL*10^(n-n/2) + aR) * (bL*10^(n-n/2) + bR)
= aL*bL*10^(n) + aL*bR *10^(n-n/2) + aR*bL *10^(n-n/2) + aR*bR
Assume a and b has the same length, we can use a divide and conquer technique to reduce the running time.
a*b = (aL*10^(n-n/2) + aR) * (bL*10^(n-n/2) + bR)
= aL*bL*10^(n) + aL*bR *10^(n-n/2) + aR*bL *10^(n-n/2) + aR*bR
= aL*bL*10^(n) + [(aL+aR)*(bL+bR) - aL*bL - aR*bR] * 10^(n-n/2) + aR*bR
Another
Consider another concise solution, see here. It used a integer array with length m+n to store each digits of the result. Then process this char array from least significant digit to most significant digit. This solution is concise, because it does not need string addition. However, each element in the integer array also has a limit, at some extreme cases, this algorithm may fail.
Another
Consider another concise solution, see here. It used a integer array with length m+n to store each digits of the result. Then process this char array from least significant digit to most significant digit. This solution is concise, because it does not need string addition. However, each element in the integer array also has a limit, at some extreme cases, this algorithm may fail.
No comments:
Post a Comment