C++ 9ms simple solutions w/wo vector


  • 0

    Two flavors of the same idea: just do it the same way we do manual calculations.

    (1) Using a vector:

    string multiply(string num1, string num2) {
            vector<int> ans(num1.length() + num2.length(), 0); // max possible length for ans is nums.length() + nums.length()
            
            for (int i1 = num1.length() - 1; i1 >= 0; i1--) {
                for (int i2 = num2.length() - 1; i2 >= 0; i2--) {
                    ans[i1 + i2 + 1] += (num1[i1] - '0') * (num2[i2] - '0');
                    ans[i1 + i2] += ans[i1 + i2 + 1] / 10;
                    ans[i1 + i2 + 1] %= 10;
                }
            }
            
            string str = "";
            for (int i = 0; i < ans.size(); i++) {
                if (str.size() || ans[i]) { str.push_back('0' + ans[i]); }
            }
            return str.empty() ? "0" : str;
    }
    

    (2) Only using string:

    string multiply(string num1, string num2) {
            string ans = string(num1.length() + num2.length(), '0');
            
            for (int i = num1.length() - 1; i >= 0; i--) {
                for (int j = num2.length() - 1; j >= 0; j--) {
                    int tempInt = (num1[i] - '0') * (num2[j] - '0') + (ans[i + j + 1] - '0');
                    ans[i + j + 1] = '0' + tempInt % 10;
                    ans[i + j] += tempInt / 10;
                }
            }
            
            size_t found = ans.find_first_not_of('0');
            if (found == string::npos) { return "0"; }
            return ans.substr(found);
    }
    

  • 0
    H

    Good one.
    One confusion on (2):

    ans[i + j] += tempInt / 10;
    

    Shouldn't this be:

    ans[i + j] = '0' + (ans[i + j] - '0' + tempInt/10)
    

    ?


  • 0

    @hezhoufan
    ans[i + j] may get overflows ( get larger than 9) in the middle of the process, so I directly increased the value instead.


Log in to reply
 

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