Memory Limit Exceed in Vector C++

Question

I'm getting memory limit exceeded error for this code. I can't find the way to resolve it. If I'm taking a long long int it gives the same error.
Why this error happening?

#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
    ///1000000000000 500000000001 getting memory limit exceed for this test case.

    ll n,k;
    cin>>n>>k;
    vector<ll> v;
    vector<ll> arrange;


    for(ll i=0;i<n;i++)
    {
        v.push_back(i+1);
    }

    //Arranging vector like 1,3,5,...2,4,6,....
    for(ll i=0;i<v.size();i++)
    {
        if(v[i]%2!=0)
        {
            arrange.push_back(v[i]);
        }
    }
    for(ll i=0;i<v.size();i++)
    {
        if(v[i]%2==0)
        {
            arrange.push_back(v[i]);
        }
    }
    cout<<arrange[k-1]<<endl; // Found the kth number.

    return 0;
}

You are allocating two vectors with 1000000000000 elements - that's quite a lot of memory you require. You should try to rethink your approach, you can probably do this with only one vector (or perhaps even without any vectors at all) — UnholySheep, May 31 '20 at 10:09
[Why should I not #include ?](https://stackoverflow.com/q/31816095/5910058) — Jesper Juhl, May 31 '20 at 10:23
Is that 1 trillion long long int that you want to store per std::vector? How much RAM do you have on your computer? I doubt you could afford a computer with that much RAM. — stackoverblown, May 31 '20 at 10:33
If it's a competitive programming question, note that you do not need to actually generate something if you are asked to find one of its properties. Also instead of the macro, a better approach for type aliases would be to use `typedef long long int ll`. Also try to not use namespace std. — Amal K, May 31 '20 at 10:59

score 1 · Answer 1 · answered May 31 '20 at 11:30

The provided code solves a coding problem for small values of n and k. However as you noticed it does fail for large values of n. This is because you are trying to allocate a couple of vectors of 1000000000000 elements, which exceeds the amount of memory available in today's computers.

Hence I'd suggest to return to the original problem you're solving, and try an approach that doesn't need to store all the intermediary values in memory. Since the given code works for small values of n and k, you can use the given code to check whether the approach without using vectors works.

I would suggest the following steps to redesign the approach to the coding problem:

Write down the contents of arrange for a small value of n
Write down the matching values of k for each element of arrange
Derive the (mathematical) function that maps k to the matching element in arrange
- For this problem this can be done in constant time, so there is no need for loops
- Note that this function should work both for even and odd values of k.
Test whether your code works by comparing it with your current results.

I would suggest trying the preceding steps first to come up with your own approach. If you can not find a working solution, please have a look at this approach on Wandbox.

score 0 · Answer 2 · answered May 31 '20 at 10:25

Assume long long int is a 8 byte type. This is a commonly valid assumptions. For every entry in the array, you are requesting to allocate 8 byte.

If you request to allocate 1000000000000 items, your are requesting to allocate 8 Terabyte of memory.

Moreover you are using two arrays and you are requesting to allocate more than 8 Terabyte.

Just use a lower number of items for your arrays and it will work.

Memory Limit Exceed in Vector C++

2 Answers2