TITLE:-Print Array intersection
PROBLEM:-
Given two random integer arrays, print their intersection. That is, print all the elements that are present in both the given arrays.
Note : Order of elements are not important
Line 1 : Integer N, Array 1 Size
Line 2 : Array 1 elements (separated by space)
Line 3 : Integer M, Array 2 Size
Line 4 : Array 2 elements (separated by space)
Print intersection elements in different lines
Constraints :
0 <= M, N <= 5 * 10^7
6
2 6 8 5 4 3
4
2 3 4 7
Sample Output 1 :
2
4
3
4
2 6 1 2
5
1 2 3 4 2
Sample Output 2 :
2
2
1
SOLUTION:-
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
// input1 - first array
// input2 - second array
// size1 - size of first array
// size2 - size of second array
void quickSort(int input[], int size) {
if(size==0||size==1)
return;
int counter=0;
for(int i=1;i<size;i++)
if(input[i]<input[0])
counter++;
int temp=input[counter];
input[counter]=input[0];
input[0]=temp;
int i=0,j=size-1;
while(i<counter&&j>counter)
{
if(input[i]<input[counter])
i++;
else if(input[j]>=input[counter])
j--;
else{
int temp1=input[i];
input[i]=input[j];
input[j]=temp1;
i++;
j--;
}
}
quickSort(input,counter);
quickSort(input+counter+1,size-1-counter);
}
void intersection(int input1[], int input2[], int size1, int size2) {
/* Don't write main().
* Don't read input, it is passed as function argument.
* Print the output and don't return it.
* Taking input is handled automatically.
*/
quickSort(input1,size1);
quickSort(input2,size2);
int i=0,j=0;
while(i<size1&&j<size2)
{
if(input1[i]==input2[j])
{
cout<<input1[i]<<endl;
i++;
j++;
}
else if(input1[i]>input2[j])
{
j++;
}
else
i++;
}
}
int main() {
int size1,size2;
cin>>size1;
int *input1=new int[1+size1];
for(int i=0;i<size1;i++)
cin>>input1[i];
cin>>size2;
int *input2=new int[1+size2];
for(int i=0;i<size2;i++)
cin>>input2[i];
intersection(input1,input2,size1,size2);
return 0;
}