Sharing my 8ms C++ accepted solution


  • 1
    0

    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);
    	}
    };

  • 0
    J

    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();
        }
    };

Log in to reply
 

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