3

For a particular problem, I have to take string input from the user which can be of size between 1 and 10^5 . I used the following code

char *a;
a = malloc(100000*sizeof(char));

and inside a loop ( t refers to number of test cases )

while( t-- )
{
  scanf( "%d", &n );
  scanf( "%s", a );
  .....
}

n is the length of the string that is input by the user at run time. The problem is this is giving me "Time Limit Exceeded"

I made few changes to the above code,

 while( t-- )
 {
   scanf( "%d", &n );
   char a[n];
   scanf( "%s", a );
   ....
 }

This works perfectly fine without "TLE" . But I don't understand why. The reason for using the first code was that time would be saved since allocation of memory is done only once. Am I wrong? Please explain.

Blisskarthik
  • 1,246
  • 8
  • 20
akashrajkn
  • 2,295
  • 2
  • 21
  • 47
  • 1
    Who is giving the "time limit exceeding" error? I think this is not a problem with your C code but with the platform you are using. – Emanuele Paolini Jul 05 '14 at 05:55
  • 1
    If the string read as `a` in the second snippet really is `n` chars wide, you're under allocating by one (the terminator). Secondly, there is no "dynamic" runtime allocation in the second case. It is literally a `sub esp,n`. Were I to guess, the TLE avoidance is likely directly related to your under allocation causing an buffer overflow and overwrite of `t` setting it to the terminator (which is 0) and thus ending your loop after a single iteration. – WhozCraig Jul 05 '14 at 05:55
  • Minor: Use `a = malloc(100000 + 1); – chux - Reinstate Monica Jul 05 '14 at 06:06
  • "Time limit exceeded" was given in www.codechef.com... The second snippet is working perfectly fine. The first snippet is giving Time Limit Exceeded... – akashrajkn Jul 05 '14 at 20:19

1 Answers1

6

If you use malloc, the memory space will create on HEAP.

While in the second implementation, the memory locates on STACK.

As I know, stack is faster than heap.

Ref: What and where are the stack and heap?

More over, I think declaring the char array outside the loop is more reasonable:

char a[100000] = {};

while( t-- )
 {
   scanf( "%d", &n );
   scanf( "%s", a );
   ....
 }
Community
  • 1
  • 1
Alfred Huang
  • 17,654
  • 32
  • 118
  • 189
  • 3
    Were the `malloc` in the loop this would be a decent argument. It isn't, therefore it... isn't. It is a single-shot allocation and contributes at-worst O(1) complexity to the general algorithm. – WhozCraig Jul 05 '14 at 06:00