Write a c program to find common elements in two arrays.
Given two positive integer arrays arr1 and arr2 of lengths len1 and len2. We have to write a c code to find intersection of these two arrays. Both the arrays are sorted.
Let’s assume we have following two sorted arrays arr1 and arr2.
int arr1[] = {2, 3, 4, 5, 6};
int arr2[] = {4, 6, 7, 8, 9};
So the common elements in these two arrays is 4 and 6.
C Program to Find Common Elements in Two Arrays
First Method (Naive Approach) – Find Common Elements in Two Arrays using Two For Loops
In this approach, we take each element of a first array and compare with every element of a second array. If it is found in second array then it’s a common element else we move to next element.
The time complexity of this approach is O(mn), Where m and n are the number of elements in array1 and array2.
C Program to Find Missing Number in Array
Java Program to Find Intersection of Two Arrays
Find Common Elements in Three Sorted Arrays
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
/** * Find Common Elements in Two Sorted Arrays */ #include <stdio.h> int printCommon(int arr1[], int len1, int arr2[],int len2) { int i,j; for(i = 0; i < len1 ;i++) { for(j = 0; j < len2 ;j++) { if(arr1[i] == arr2[j]){ printf("\n Common elements is %d", arr1[i]); } } } } int main(void) { /* * For demostration purpose, i take these values in a code * / int arr1[] = {2,3,4,5,6}; int arr2[] = {4,6,7,8,9}; // Lenght of arr1 and arr2 int len1 = 5; int len2 = 5; printCommon(arr1,len1,arr2,len2); return 0; } |
Second Method -Find Common Elements in Two Arrays of Different Length/Size
Implementation Logic:
i) Use two index variables i and j, Initialized them with 0.
ii) If arr1[i] is smaller than arr2[j] then increment i.
iii) If arr1[i] is greater than arr2[j] then increment j.
iv) If both are same then print any of the array value and increment both i and j.
Program to implement a stack using an array
The time complexity of this approach is O(m+n).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <stdio.h> /* Prints intersection of two arrays arr1[] and arr2[] len1 is the number of elements in arr1[] len2 is the number of elements in arr2[] */ int printCommon(int arr1[], int len1, int arr2[], int len2) { int i=0,j=0; while(len1 > i && len2 > j){ if (arr1[i] < arr2[j]) { i++; }else if(arr2[j] < arr1[i]){ j++; } else { printf("\nCommon element is %d",arr1[i]); i++; j++; } } } int main(void) { int arr1[] = {2,3,4,5,6}; int arr2[] = {4,6,7,8,9}; /* Length of first and second array. */ int len1 = 5; int len2 = 5; printCommon(arr1, len1, arr2, len2); return 0; } |
Program to search an element in an array
Programming questions on linked list
Conclusion
In this tutorial, I have explained two approaches to solve this problem. If you know some other method please let us know through your comments.
