maximum size of an array

can anyone tell me what is the maximum size of different types(bool,int,long long …etc ) of array (or vector) we can take in c++

5 Likes

array size 10^7 to 10^8 declared globally(i.e. on heap) is possible…if u declare nething in the main or in ne fxn…it goes into the stack which has a smaller size hence ur 10^7 array did not work out…try declaring it globally and it should work…this is what i have observed…hope this helps…:slight_smile:

24 Likes

Have noticed something in SPOJ. I think codechef is similar to that so this will help.

[http://www.spoj.com/forum/viewtopic.php?f=41&t=9851][1]

As I have already mentioned, its something from 10^6 to 10^7 depending on the stack size.

As mentioned on codechef wiki,

We use the SPOJ online judge as our backened.

It is therefore clear that the stack size is 256MB.
[1]: http://www.spoj.com/forum/viewtopic.php?f=41&t=9851

3 Likes

//here is my code
#include
#include
using namespace std;
#define MAX 100000
bool v[MAX];
void pre()
{

for(int i=2;i<MAX;i++)v[i]=true;
for(int i=2;i<MAX;i++)
{
	if(v[i])
	for(int j=i;j*i<MAX;j++)
	v[j*i]=false;
}

}
int main()
{
pre();
int i;
cin>>i;
cout<<i;
return 0;
}

check this link

Code chef runs on SPOJ server’s. SPOJ has 2 server clusters on which submissions are run , 1 old 733 Mhz cluster which has a memory limit of 256 mb and a newer cluster of 3Ghz with a memory limit of 1.5 gb.

Most practice problems run on the older cluster of limit 256mb and array size limit will most probably be around 6 * 10^7 which occupies around 230-240mb of memory. i have tried [10^5][600]and it has worked for me.
Most of the current contests run on the newer cluster of size 1.5 gb but limits for maximum size of a single array is still around 10^7 to 10^8 as it is very difficult to allot contiguous memory locations . However as total memory limit is around 1.5 gb , you may be able to declare around multiple (5 or 6) arrays of this length .

If you need that much memory ,my suggestion is that you declare multiple arrays of size around 6*10^6 for contest problems.

4 Likes

@all Usually 1-D array of size 10^6 or 7 works fine but what if i want to allocate a 2-d array whose max size can be upto [10^6][10^6]. That aint gonna work probbaly… so if i allocate two 1-D arrays of size 10^6, they work fine… However the space allocated in memory for both are same i suppose if not allocated dynamically. Why such happens?

@anonymousins Usually if you are taking the array for i/p and that doesnt require manipulation, simply take a variable of the specified datatype and overwrite it the number of times required. I mean this .

for(i=0;i<n;i++) cin>>ele;

You could have taken an array for ele as int ele[n], but the above is much better. Also, there are many more strategies to do,but that depends on the type of question it is.

I am getting the same error on allocating array of size 100001. It shows runtime error on codechef and program stops working in devc++
Here’s snippet of the code:

#include<bits/stdc++.h>
using namespace std;
bool prime[100001];
int k=0;
void sieve(){
	prime[1]=true;
	prime[0]=true;
	for(int i=2;i<=100000;i++){
		if(prime[i]==false){
			for(int j=i*i;j<=100000;j=j+i){
				prime[j]=true;
			}
		}
	}
}
1 Like

Its beacuse of your

for(int j=i*i;j<=100000;j++) loop

Here your i*i goes out of int bounds and a overflow occurs. Try taking both i and j as long int and it should work fine.

2 Likes

Thanks! it helped

depends on your stack size in linux to increase your stack size to unlimited or a particular value use ulimit -s then it will work make sure value is > what ever array space you require plus your auto variables plus return frames etc blah …

I have tried with 10^6 and it works… but for 10^7 it isn’t… so it lies something in between. Waiting for someone to answer this. :smiley:

1 Like

i dont know why my program stops working with size 10^5 even if with bool arry

@princerk…can u give ur code where this happens!!!

but when i run the code given it stops working im using devcpp…can i increase the size of an array explicitly

Could you give a link to your code as it would be better to understand. Also what error are you getting?

tnx @kcahdog …can u tell me why the above code giving runtime error on ideone when i decrease MAX to 10^4 it runs.

i have given the link

I do not know why that code gave an error. However i declared that array as local and it ran fine. Here is the link http://ideone.com/286OTE .

My best guess is ideone restricts the amount of global memory accessible to users while the full 256 mb can be used for local variables/arrays. This might be done to easily manage each submission locally as it will prevent everyone from using too much common memory.

There is nothing wrong with the code. I guess it’s just because the ideone is designed like this.

finally i found out the bug…actully this is the int overflow.when i take MAX
10^6 (i*j overflow) when i chage ‘i’ and ‘j’ to long long it runs without error. tnx a lot @kcahdog