Finding the common elements in two arrays

Finding the common elements in two arrays is akin to finding the intersection of two sets. Let's learn how to do it.

How to do it…

1. Define two arrays of a certain size and assign elements of your choice to both the arrays. Let's assume that we created two arrays called p and q, both of size four elements:

Figure 1.11

2. Define one more array. Let's call it array r, to be used for storing the elements that are common between the two arrays.
3. If an element in array p exists in the array q, it is added to array r. For instance, if the element at the first location in array p, which is at p[0], does not appear in array q, it is discarded, and the next element, at p[1], is picked up for comparison.

4. And if the element at p[0] is found anywhere in array q, it is added to array r, as follows:

Figure 1.12

5. This procedure is repeated with other elements of array q. That is, p[1] is compared with q[0], q[1], q[2], and q[3]. If p[1] is not found in array q, then before inserting it straightaway into array r, it is compared with the existing elements of array r to avoid repetitive elements.
6. Because the element at p[1] appears in array q and is not already present in array r, it is added to array r as follows:

Figure 1.13

The commoninarray.c program for establishing common elements among the two arrays is as follows:

#include<stdio.h>
#define max 100

int ifexists(int z[], int u, int v)
{
    int i;
    if (u==0) return 0;
    for (i=0; i<=u;i++)
        if (z[i]==v) return (1);
    return (0);
}
void main()
{
    int p[max], q[max], r[max];
    int m,n;
    int i,j,k;
    k=0;
    printf("Enter the length of the first array:");
    scanf("%d",&m);
    printf("Enter %d elements of the first array\n",m);
    for(i=0;i<m;i++ )
        scanf("%d",&p[i]);
    printf("\nEnter the length of the second array:");
    scanf("%d",&n);
    printf("Enter %d elements of the second array\n",n);
    for(i=0;i<n;i++ )
        scanf("%d",&q[i]);
    k=0;
    for (i=0;i<m;i++)
    {
        for (j=0;j<n;j++)
        {
           if (p[i]==q[j])
           {
               if(!ifexists(r,k,p[i]))
               {
                   r[k]=p[i];
                   k++;
               }
            }
        }
    }
    if(k>0)
    {
        printf("\nThe common elements in the two arrays are:\n");
        for(i = 0;i<k;i++)
            printf("%d\n",r[i]);
    }
    else
        printf("There are no common elements in the two arrays\n");
}

Now, let's go behind the scenes to understand the code better.

How it works...

A macro, max, is defined of size 100. A function, ifexists(), is defined that simply returns true (1) or false (0). The function returns true if the supplied value exists in the specified array, and false if it doesn't.

Two arrays are defined, called p and q, of size max (in other words, 100 elements). You will be prompted to specify the length of the array, p, and then asked to enter the elements in that array. After that, you will be asked to specify the length of array q, followed by entering the elements in array q.

Thereafter, p[0], the first element in array p , is picked up, and by using the for loop, p[0] is compared with all the elements of array q. If p[0] is found in array q, then p[0] is added to the resulting array, r.

After a comparison of p[0], the second element in array p, p[1], is picked up and compared with all the elements of array q. The procedure is repeated until all the elements of array p are compared with all the elements of array q.

If any elements of array p are found in array q, then before adding that element to the resulting array, r, it is run through the ifexists() function to ensure that the element does not already exist in array r. This is because we don't want repetitive elements in array r.

Finally, all the elements in array r, which are the common elements of the two arrays, are displayed on the screen.

Let's use GCC to compile the commoninarray.c program as follows:

D:\CBook>gcc commoninarray.c -o commoninarray

Now, let's run the generated executable file, commoninarray.exe, to see the output of the program:

D:\CBook>./commoninarray
Enter the length of the first array:5
Enter 5 elements in the first array
1
2
3
4
5

Enter the length of the second array:4
Enter 4 elements in the second array
7
8
9
0

There are no common elements in the two arrays

Because there were no common elements between the two arrays entered previously, we can't quite say that we've truly tested the program. Let's run the program again, and this time, we will enter the array elements such that they have something in common.

D:\CBook>./commoninarray
Enter the length of the first array:4
Enter 4 elements in the first array
1
2
3
4

Enter the length of the second array:4
Enter 4 elements in the second array
1
4
1
2

The common elements in the two arrays are:
1
2
4

Voilà! We've successfully identified the common elements between two arrays.