A clean and efficient solution accepted as best submission in C, well-explained


  • 11

    In fact before we truly hack this problem, we might remember other calculations for [linked list][1] and [binary strings][2] and trying to reuse that kind of pattern; but soon we will find out that will cost much energy and time to solve this one: multiply for each digits, move one step for the next digit and then add them, so annoying and tedious.

    So we will try another naive one to easily hack this, imitating the multiplication process we human do but convert it a little bit for easier latter work. The following steps will use 34 * 56 to present the whole process:

    • first, we multiply the lowest digit 6 with all the first number 34 without any carry just store the numbers: 18, 24 - from left to right respectively (all the carry operations will be handled in the following steps); then the second lowest digit 5 and the result numbers will be 15, 20 from left to right respectively;
    • second, actually when we human calculate, (15, 20) as a whole will be moved to the left by one digit, right? Why? Because digit 5 is left-er than the digit 6 by one digit; okay, things are now getting clearer now; here we are going to use an array to store the result of each position , still ignoring carry here; one thing should be remembered is that the position is determined by the position of the digit in both the first and second number; if you know how the multiplication process, then this will be easy to understand.
    • third, we are almost there; strings are indexed from left to right, so the smaller the index of the digit the higher its digit base (100, 10, 1 etc) will be; so we will store the results following this fact, from left to right, the unit will be decreasing; as we have discussed in second part, the position will be determined by that of digits in both first and second number so arr[i+j] = (num1[i]-'0')*(num2[j]-'0') will be a good equation; but the same position might be used to store several results from different pairs of digits multiplication. So arr[i+j] += (num1[i]-'0')*(num2[j]-'0') and before we collect the results, we have to initialise all elements of arr to zero; at last arr[i+j+1] should be used instead of arr[i+j], why? we might have a carry at the heading position, right? You will understand it sooner or later after all the specification;
    • fourth, collecting the result and constructing the result string to return: from the last to the first we get carried by a[i-1] = a[i]/10; a[i] %= 10; but the zero position here might be zero for no carry comes around so we should remove it, if it is that case otherwise we just collect it as usual.

    • Space cost O(n)
    • Time cost O(n)
    //AC - 4ms;
    char* multiply(char* num1, char* num2){
        if(*num1=='0' || *num2=='0') return "0";
        int len1 = strlen(num1);
        int len2 = strlen(num2);
        int len = len1+len2;
        int *arr = (int*)malloc(sizeof(int)*len); //the number of digits of the result - len is the top;
        memset(arr, 0, sizeof(int)*len); //this is critical;
        for(int i=len1-1; i > -1; i--)
            for(int j=len2-1; j > -1; j--)
                arr[i+j+1] += (num1[i]-'0')*(num2[j]-'0'); //collect result of each position;
        for(int i=len-1; i > 0; i--) {
            arr[i-1] += arr[i]/10;
            arr[i] %= 10;
        }
        char *s = (char*)malloc(sizeof(char)*(len+1)); //converting the digits result to string;
        int index = 0;
        int i = 0;
        if(arr[i]==0) i++; //in case the zero position has no carry, if it does, ignore it;
        while(i < len)
            s[index++] = arr[i++]+'0';
        s[index] = '\0';
        return s;
    }
    

  • 0
    Z

    So clean and smar! Thanks for your sharing.


  • 0
    Z

    very beautiful solution


  • 0

    C++ solution as follows:

    class Solution {
    public:
        //AC - 8ms - careful about the corner cases;
        string multiply(string num1, string num2) {
            string s;
            vector<int> v(num1.size()+num2.size()-1, 0);
            for(int i = num1.size()-1; i >= 0; --i)
    			for(int j = num2.size()-1; j >= 0; --j)
    				v[i+j] += (num1[i]-'0') * (num2[j]-'0');
            for(int i = v.size()-1; i > 0; --i) {
                v[i-1] += v[i] / 10;
                v[i] %= 10;
            }
            if(v[0] == 0) return "0"; //started with '0', it must be zero;
            if(v[0] / 10) {//there is still a carrier to be collected;
                s += to_string(v[0]/10);
                v[0] %= 10;
            }
            for(int i = 0; i < v.size(); ++i) s += to_string(v[i]);
            return s;
        }
    };
    

  • 0
    H

    @LHearen said in A clean and efficient solution accepted as best submission in C, well-explained:

    int arr = (int)malloc(sizeof(int)*len); //the number of digits of the result - len is the top;
    memset(arr, 0, sizeof(int)*len); //this is critical;

    Great solution! Note that the stdlib function calloc will automatically initialize allocated memory to 0 which means you can replace the following 2 lines:

    int arr = (int)malloc(sizeof(int)*len); //the number of digits of the result - len is the top;
    memset(arr, 0, sizeof(int)*len); //this is critical;

    with

    int *arr = (int *)calloc(sizeof(int) * len, sizeof(int));


Log in to reply
 

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