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++

1 Like

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

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:

9 Likes

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

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

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

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.

3 Likes

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

@princerk i dont think you would be able to increase the stack size of those in codechef… Try some other optimization techniques…

@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?

@kcahdog @princerk Can you give example of any such code that clears my above doubt.

@damn_me when u allocate an array of size [10^6][10^6] it will take (10^6)*(10^6) i.e 10^12 which is very much greater then two 1-D arrays of size [10^6] i.e 2 * (10^6) i think it clears ur doubt

So as all codechef problems have input data in the order of 10^8, array can’t be used to store input data.So what are the other strategies?I am not able to solve problems bcoz of this and i am stuck from 2 weeks or so.Please help…

@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.

//