Write a C, C++ program to find intersection of two arrays. Given a two sorted arrays, we need to write a code to find intersection of two arrays.
Suppose, we have given following two arrays.
int arr1[] = { 1, 3, 4, 5}
int arr2[] = { 1, 2, 3, 4, 5}
Intersection of arr1 and arr2 is 1, 3, 4, 5.
Let's discuss how to solve this problem.
Practice question on arrays
C, C++ interview questions
METHOD 1: Naive approach
Easiest approach is to solve this problem using two for loops. But the time complexity of using two for loops is O(n2).
METHOD 2:
1. Use two indexes p and q.
2. Run a while loop and check
a) If firstarray[p] > secondarray[q] then increment q.
b) If secondarra[q] > firstarray[p] then increment p.
c) If firstarray[p] == secondarray[q] then increment p and q.
Time complexity of this solution is O(m + n), where m and n is the length of first and second array.
Sorting algorithms and their time complexity .
Let's implement method 2 solution.
Output :
Enter length of first array (Max 100) : 4
Enter sorted values for first array :
1
3
4
5
Enter length of second array (Max 100): 5
Enter sorted values for second array :
1
2
3
4
5
Intersection of two arrays : 1 3 4 5
Suppose, we have given following two arrays.
int arr1[] = { 1, 3, 4, 5}
int arr2[] = { 1, 2, 3, 4, 5}
Intersection of arr1 and arr2 is 1, 3, 4, 5.
Let's discuss how to solve this problem.
Practice question on arrays
C, C++ interview questions
How to Find Intersection of Two Arrays
METHOD 1: Naive approach
Easiest approach is to solve this problem using two for loops. But the time complexity of using two for loops is O(n2).
/* Suppose len1 and len2 is the length of first and second array. */ for(int i=0; i < len1; i++) { for(int j = 0; j < len2; j++) { if( arr1[i] == arr2[j] ) { cout << arr1[i]; } } }
METHOD 2:
1. Use two indexes p and q.
2. Run a while loop and check
a) If firstarray[p] > secondarray[q] then increment q.
b) If secondarra[q] > firstarray[p] then increment p.
c) If firstarray[p] == secondarray[q] then increment p and q.
Time complexity of this solution is O(m + n), where m and n is the length of first and second array.
Sorting algorithms and their time complexity .
Let's implement method 2 solution.
Find Intersection of Two Arrays in C++
#include <iostream> using namespace std; int main() { int arr1[100], arr2[100], len1, len2, i, p = 0, q = 0; cout << "Enter lenght of first array (Max 100) \n"; cin >> len1; cout << " Enter sorted values for first array \n"; for (i = 0; i < len1; i++) { cin >> arr1[i]; } cout << "Enter length of second array (Max 100) \n"; cin >> len2; cout << " Enter sorted values for second array \n"; for (i = 0; i < len2; i++) { cin >> arr2[i]; } while (p <= len1 && q <= len2) { if (arr1[p] < arr2[q]) { p++; } else if (arr2[q] < arr1[p]) { q++; } else if (arr1[p] == arr2[q]) { cout << arr1[p] <<" "; p++; q++; } } return 0; }
Output :
Enter length of first array (Max 100) : 4
Enter sorted values for first array :
1
3
4
5
Enter length of second array (Max 100): 5
Enter sorted values for second array :
1
2
3
4
5
Intersection of two arrays : 1 3 4 5
Find Intersection of Two Arrays in C
#include <stdio.h> int main(void) { int arr1[100], arr2[100], len1, len2, i, p = 0, q = 0; printf( "Enter lenght of first array (Max 100) \n"); scanf( " %d ", &len1); printf( " Enter sorted values for first array \n"); for (i = 0; i < len1; i++) { scanf(" %d ", &arr1[i]); } printf( "Enter length of second array (Max 100) \n"); scanf (" %d ", &len2); printf (" Enter sorted values for second array \n"); for (i = 0; i < len2; i++) { scanf( " %d ", &arr2[i]); } while (p <= len1 && q <= len2) { if (arr1[p] < arr2[q]) { p++; } else if (arr2[q] < arr1[p]) { q++; } else if (arr1[p] == arr2[q]) { printf (" %d ", arr1[p]); p++; q++; } } return 0; }
No comments:
Post a Comment