# Multiply Strings ## # Solution

### # Int Array

Use an int array to store the result and convert back to string.

EPI in Python, page 44

We use the grade-school algorithm for multiplication: multiply the 1st number by each digit of the second, and then add all the resulting terms.

From a space perspective, it is better to incrementally add the terms rather than compute all of them individually and then add them up. The number of digits required for the product is at most for and digit operands, so we use an array of size for the result.

Thus, res[i+j+1] is assigned w/ the mod of sum(2 digits' product plus current digit at res[i+j+1]), and res[i+j] is assigned w/ the carry of sum plus current digit at res[i+j].

See graph explanation at here.

def multiply(self, num1: str, num2: str) -> str:
if (num1=="0" or num2=="0"): return "0"
prod = *(len(num1)+len(num2))
for i in range(len(num1)-1,-1,-1):
for j in range(len(num2)-1,-1,-1):
pos1,pos2 = i+j,i+j+1
mul = int(num1[i])*int(num2[j])
sum = mul + prod[pos2]
prod[pos1] += sum//10
prod[pos2] = sum%10

res = ""
for i,p in enumerate(prod):
if not (i==0 and p==0):
res += str(p)

return res


### # String as Char Array

We could calculate product of int digits and store in string.

Since str object in Python doesn't support item assignment, here is a C++ solution below:

string sum(num1.size() + num2.size(), '0');

for (int i = num1.size() - 1; 0 <= i; --i) {
int carry = 0;
for (int j = num2.size() - 1; 0 <= j; --j) {
int tmp = (sum[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0') + carry;
sum[i + j + 1] = tmp % 10 + '0';
carry = tmp / 10;
}
sum[i] += carry;
}

size_t startpos = sum.find_first_not_of("0");
if (string::npos != startpos) {
return sum.substr(startpos);
}
return "0";

Last Updated: 5/13/2020, 7:39:18 AM