I need to pass a programming exam in order to graduate but I'm having a hard time passing it because most of my programs are too slow. Can someone give me some tips on how to make my programs faster please? Below is an example of a question we had in the last exam and the code i wrote. My code passed the first test case but for the other 3 it exceeded the time limit. Please let me know if you have any suggestions on how to improve my code.
Description
Given two sets of numbers, output their intersection set.Input
There are multiple test cases. Each case contains four lines. The first line begins with an integer N. The second line contains N integers, representing the numbers in the first set. The third line has one integer M, and the fourth line contains M integers, represent the numbers in the second set.All the numbers are 32 bit signed integers.
The input is terminated if N = 0.
For case 1, 1 <= N, M <= 10^3 (Time Limit: 1 sec)
For case 2, 1 <= N, M <= 10^4 (Time Limit: 1 sec)
For case 3, 1 <= N, M <= 10^5 (Time Limit: 1 sec)
For case 4, 1 <= N, M <= 10^6 (Time Limit: 3 sec)Output
For each test case, print the intersection of the two sets. Output them in ascending order. If the intersection of the two sets is an empty set, print 「empty」 (without quotes).Sample Input
3
1 2 3
3
4 5 6
8
4 10 13 8 9 2 1 5
4
4 2 3 1
5
1 2 2 3 2
5
1 2 2 3 1
0Sample Output
empty
1 2 4
1 2 2 3
This is my code:
#include<stdio.h>
#include<stdlib.h>
int set1[2][1000000];
int set2[2][1000000];
int intersection[1000000];
int main()
{
int n;
scanf("%d",&n);
while( n!= 0)
{
int m, i, x, num, y = 0;
int w, u, xx;
for(i = 0; i < n; i++) //initialise set1 to 0
{
set1[1][i] = 0;
}
for(x = 0; x < n; x++) //put set1 in array
{
scanf("%d", &num);
set1[0][x] = num;
}
scanf("%d",&m);
for(i = 0; i < m; i++) //initialise set2 to 0
{
set2[1][i] = 0;
}
for(x = 0; x < m; x++) //put set2 in array
{
scanf("%d", &num);
set2[0][x] = num;
}
for(x = 0; x < n; x++)
{
for(i = 0; i < m; i++)
{
if((set1[1][x] == 0) && (set1[0][x] == set2[0][i]) && (set2[1][i] == 0))
{
intersection[y] = set2[0][i];//put in printing array
y++;
set2[1][i] = 1;
set1[1][x] = 1;
}
}
}
for(x = 0; x < y; ++x) //sort
{
for(i = x + 1; i < y; ++i)
{
if(intersection[x] > intersection[i])
{
w = intersection[x];
intersection[x] = intersection[i];
intersection[i] = w;
}
}
}
for(x = 0; x < y; x++)//print
{
if(x == 0)
{
printf("%d", intersection[x]);
}
else printf(" %d", intersection[x]);
}
if (y == 0)
{
printf("empty");
}
printf("\n");
scanf("%d",&n);
}
return 0;
}
while
loop. Sorry. \$\endgroup\$