TJU 3108 Common item Solution

Problem Description :

    The problem is about to find Intersection of two sets of number. We have to  just find out number of common elements of two sets.

    Idea 1:(Naive)

        Just for every elements of set A we can find out is there any element of set B is equal to that number or not. Finally,as the problem set ,we will print the common elements in increasing order. It will take O(N*M)times where  N is the number of elements of set A and M is the number of elements of set B. And finally sorting cost.

    Idea 2:(Sorting A then binary search)

       This approach is comparatively faster then approach 1. Here, we will sort the set A. We can do it using a O(N*logN) time algorithm where N is the number of elements of A.Then for every elements of B we will just search set A using binary search. So, searching all elements of B will takes O(M*logN) times where M is the number of elements of set B. And finally we will have to sort the final answer.

    Idea 3:

         We can sort both set A and B. Then we can find out the common elements easily and also as the list are already sorted we will have not to sort the final common elements.

    Idea 4:(counting sort idea)

          As All numbers in the input is smaller than 1000 we can solve this problem using counting sort idea.C Implementation of Idea 4.

#include <stdio.h>

int main(){
 int ina[1002],inb[1002],cas,a,b,i,t,j,k,out[1002];

 scanf("%d",&cas);
 while(cas){
  scanf("%d %d",&a,&b);
  for( i = 0;i <= 1000; i++)ina[i]=inb[i]=0;
  for( i = 0; i < a; i++){
   scanf("%d",&t);
   ina[t]=1;
  }
  for(i = 0; i < b;i++){
   scanf("%d",&t);
   inb[t]=1;
  }
  j=0;
  for( i = 0; i <= 1000; i++)
   if(ina[i]&&inb[i])out[j++]=i;
  if(!j)printf("\n");
  else {
   for( k = 0; k < j-1; k++)printf("%d ",out[k]);
   printf("%d\n",out[j-1]);
  }
  cas--;
 }
 return 0;
}