# Sharing my 8ms C++ accepted solution

• This is an example of the pretty straightforward but very efficient C++ solution with 8ms runtime on OJ.
It seems most of people here implemented solutions with base10 arithmetic, however that is suboptimal. We should use a different base.

This was a hint. Now stop, think, and consider coding your own solution before reading the spoiler below.

The idea used in the algorithm below is to interpret number as number written in base 1 000 000 000 as we decode it from string. Why 10^9? It is max 10^n number which fits into 32-bit integer. Then we apply the same logic as we used to hate in school math classes, but on digits which range from 0 to 10^9-1.

You can compare the multiplication logic in other posted base10 and this base1e9 solutions and you'll see that they follow exactly same pattern.

Note, that we have to use 64-bit multiplication here and the carry has to be a 32-bit value as well.

``````class Solution {
public:
void toBase1e9(const string& str, vector<uint32_t>& out)
{
int i = str.size() - 1;
uint32_t v = 0;
uint32_t f = 1;
do
{
int n = str[i] - '0';
v = v + n * f;
if (f == 100000000) {
out.push_back(v);
v = 0;
f = 1;
}
else {
f *= 10;
}
i--;
} while (i >= 0);
if (f != 1) {
out.push_back(v);
}
}

string fromBase1e9(const vector<uint32_t>& num)
{
stringstream s;
for (int i = num.size() - 1; i >= 0; i--) {
s << num[i];
s << setw(9) << setfill('0');
}
return s.str();
}

string multiply(string num1, string num2)
{
if (num1.size() == 0 || num2.size() == 0)
return "0";
vector<uint32_t> d1;
toBase1e9(num1, d1);
vector<uint32_t> d2;
toBase1e9(num2, d2);
vector<uint32_t> result;
for (int j = 0; j < d2.size(); j++) {
uint32_t n2 = d2[j];
int p = j;
uint32_t c = 0;
for (int i = 0; i < d1.size(); i++) {
if (result.size() <= p)
result.push_back(0);
uint32_t n1 = d1[i];
uint64_t r = n2;
r *= n1;
r += result[p];
r += c;
result[p] = r % 1000000000;
c = r / 1000000000;
p++;
}
if (c) {
if (result.size() <= p)
result.push_back(0);
result[p] = c;
}
}

return fromBase1e9(result);
}
};``````

• Thanks, I've rewritten your code :-)

``````class Solution {
public:
string multiply(string num1, string num2) {
if (num1.empty() || num2.empty()) return "";
vector<uint32_t> a = toBase1e9(num1);
vector<uint32_t> b = toBase1e9(num2);
vector<uint32_t> result(a.size() + b.size(), 0);
for (int i = 0; i < a.size(); i++) {
for (int j = 0; j < b.size(); j++) {
uint64_t t = uint64_t(a[i]) * uint64_t(b[j]) + result[i+j];
result[i+j] = t % 1000000000;  // mod 1e9
result[i+j+1] += t / 1000000000;  // div 1e9
}
}
return fromBase1e9(result);
}
vector<uint32_t> toBase1e9(string s) {
vector<uint32_t> v;
uint32_t value = 0;
uint32_t factor = 1;
for (auto it = s.rbegin(); it != s.rend(); it++) {
value += (*it - '0') * factor;
if (factor != 100000000) {  // != 1e8
factor *= 10;
} else {
v.push_back(value);
value = 0;
factor = 1;
}
}
if (factor != 1) v.push_back(value);
return v;
}
string fromBase1e9(vector<uint32_t> v) {
stringstream ss;
while (v.size() > 1 && v.back() == 0) v.pop_back();
for (auto it = v.rbegin(); it != v.rend(); it++) {
ss << *it;
ss << setw(9) << setfill('0');
}
return ss.str();
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.