# Time limit

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

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.

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

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

3 Likes

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

//