Memory limit exceeded...Why?


  • 1
    Z
    class Solution {
        public:
            string mul(string a, char b) {
                string res;
                int carry = 0;
                for(int i = a.size(); i >= 0; --i) {
                    int t = (b - '0') * (a[i] - '0') + carry;
                    int digit = t % 10;
                    carry = t / 10;
                    char ch = '0' + digit;
                    res = ch + res;
                }
                if(carry != 0) {
                    char temp = carry + '0';
                    res = temp + res;
                }
                return res;
            }
            
            string add(string a, string b) {
                int carry = 0;
                string res;
                reverse(a.begin(), a.end());
                reverse(b.begin(), b.end());
                int i = 0;
                while(i < a.size() || i < b.size()) {
                    int x = 0;
                    int y = 0;
                    if(i < a.size())
                        x = a[i] - '0';
                    if(i < b.size())
                        y = b[i] - '0';
                    int sum = x + y + carry;
                    carry = sum / 10;
                    sum = sum % 10;
                    res.push_back(sum + '0');
                }
                if(carry != 0)
                    res.push_back(carry + '0');
                reverse(res.begin(), res.end());
                return res;
            }
        
            string multiply(string num1, string num2) {
                // Note: The Solution object is instantiated only once and is reused by each test case.
                string res;
                for(int i = num2.size() - 1; i >= 0; --i) {
                    if(num2[i] == '0')//skip when one char equals 0
                        continue;
                    string t = mul(num1, num2[i]);//multiply a char in num2 and num1
                    for(int j = 0; j < num2.size() - 1 - i; ++j) {//supplement the '0's on the tail
                        t += '0';
                    }
                    res = add(res, t);//add the res and the current string
                }
                return res;
            }
        };
    

    Memory Limited Exceeded. Why?

    My algorithm is naive and easily understandable. Use every char in num2 to multiply the whole num1 and then add it to the res.

    Thank you for your help.


  • 2
    S

    I doubt you do not write your main function and run your code in local when it is not accepted. Seems too rely on the online judge result. If you run your code in local, you can find the reason.

    There is an infinite loop in your code. Which may lead to time limit exceed, however it reach the memory limit first.


  • 0
    G

    Check the while loop of your add function. I think you would like to add i++;


Log in to reply
 

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