Time limit

general
,
1

// question link TSORT Problem - CodeChef

// my program output is correct but time limit exceeds…any help or suggestion to reduce executn time
#include<stdio.h>
#define n 1000000
long a[n],b[n];
int main()

{
int e,q,m,i,w,k;

for(i=0;i<=n;i++)

a[i]=0;

scanf("%d",&q);
for(w=0;w<q;w++)
{
   
   scanf("%d",&k);
   fflush(stdin);
   if(a[k]==0)
   a[k]=k;
   else
   b[w]=k;
   }

for(e=1;e<n;e++)
{
	if(a[e]!=0)
	printf("%ld\n",a[e]);
	
	for(i=1;i<n;i++)
	{
		if((a[e]==b[i])&&b[i]!=0)
		printf("%ld\n",b[i]);

            }
}
return 0;

}

3 Likes
2

The third for loop which you are using to print the answer, has another for loop nested in it. And both the loops run from 1 to n, which means it will take O(n^2) computations to come out of this loop.
Now, as specified in the problem, the maximum value of n can be 10^6. Therefore, it will take O(10^12) computations to print the answer, which is very slow.

Read this: FAQ | CodeChef

So, all you need to do is come up with a better algorithm.
Also, while analyzing time complexity of our algorithms, we assume that the system can do approximately 10^8 computations in a second. That’s how the given time limit is used.

1 Like
3

what if i use while loop everywhere instead of for loop …???

3 Likes
4

That does not change the number of computations. Read about time complexity analysis and applications.