MLE(Memory Limit Exceeded)

I recently face MLE problem during google kickstart where my program was simple and used recursive solution in it.
How to overcome MLE?

could you share your program?

Question: https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d3f5b

My solution:
#include
#include <bits/stdc++.h>
#define ll long long int
using namespace std;

ll calc(vector<int> v,ll k){
    ll max_diff = 0;
    ll n = v.size();
    ll pos=0;
    ll new_element = 0;
    for(ll i=0;i<n-1;i++){
        if((v[i+1]-v[i]) > max_diff) {
            max_diff = (v[i + 1] - v[i]);
            new_element = v[i] + max_diff/2;
            pos = i+1;
        }
    }
    if(k==0)
        return max_diff;
    else{
        v.insert(v.begin()+pos, new_element);
        return calc(v,k-1);
    }
}

int main(){
    ll t;
    cin>>t;
    vector<int> v;
    for(ll z = 1; z<=t; z++)
    {
        v.clear();
        ll n,k;
        cin>>n>>k;
        ll ab;
        for(ll i=0;i<n;i++){
          cin>>ab;
          v.push_back(ab);
        }
        ll answer = calc(v,k);
        cout<<"Case #"<<z<<": "<<answer<<endl;
    }
}

How to overcome MLE :- use less memory!
I haven’t gone through your program but it seems may be you are inserting more values than you should in the vector v.

I can see that every time you are calling calc function a new vector v is created, try passing the vector by reference it might be the bug you are looking for

1 Like