Given two random integer arrays, print their intersection. That is, print all the elements that are present in both the given arrays. Input arrays can contain duplicate elements.

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.

Input arrays can contain duplicate elements.

Note : Order of elements are not important

Input format :

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)

Output format :

Print intersection elements in different lines

Constraints :

0 <= M, N <= 5 * 10^7

Sample Input 1 :

6
2 6 8 5 4 3
4
2 3 4 7 

Sample Output 1 :

2 
4 
3

Sample Input 2 :

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;
}




• Tweet
• Share
• Share
• Share
• Share

About Admin MC3

This is dummy text. It is not meant to be read. Accordingly, it is difficult to figure out when to end it. But then, this is dummy text. It is not meant to be read. Period.

Related Post