Perform Set Operations on Arrays

Perform Set Operations on Arrays

In this problem, we'll be performing some basic set operations on the given arrays like Union, Intersection, and Difference. I found this problem when I was writing a practice test on ADT (Array as a Data Structure).

Examples Set Operations

Array1: 2 9 21 28 35
Array2: 2 3 9 18 28

Union(A1∪A2)
2 3 9 18 21 28 35

Intersection(A1∩A2)
2 9 28

Difference(A1-A2)
21 35

Union ∪

A union of two sets will contain the result of elements present in both the sets, but by their nature sets do not contain duplicates hence no repeated values.

If, A = {1,2,3} B={1,3,5} then A ∪ B = {1,2,3,5}

Intersection ∩

As the name says, the intersection of two sets will give us the values/elements present in both the sets.

If, C = {6,8,9} C={8,9,11} then C ∩ D = {8,9}

Difference -

The difference operation is nothing but subtraction, this usually results in the elements of first set excluding similar elements present in the other set.

If, E = {4,8,11} F={8,9,12} then E - F = {4,11}

Program for Set Operations

I've written this code in C however the logic remains the same in C++, python, or any other language

#include <stdio.h>
#include <stdlib.h>

//set operations
struct Array
{
    int A[10];
    int size;
    int length;
};

void Display(struct Array arr)
{
    int i;
    printf("Elements are\n");
    for (i = 0; i < arr.length; i++)
        printf("%d ", arr.A[i]);
}

struct Array *Union(struct Array *arr1, struct Array *arr2)
{
    int i, j, k;
    i = j = k = 0;
    //join both arrays
    struct Array *arr3 = (struct Array *)malloc(sizeof(struct Array));
    while (i < arr1->length && j < arr2->length)
    {

        if (arr1->A[i] < arr2->A[j])
            arr3->A[k++] = arr1->A[i++];
        else if (arr2->A[j] < arr1->A[i])
            arr3->A[k++] = arr2->A[j++];
        else
        {
            arr3->A[k++] = arr1->A[i++];
            j++;
        }
    }
    for (; i < arr1->length; i++)
        arr3->A[k++] = arr1->A[i];
    for (; j < arr2->length; j++)
        arr3->A[k++] = arr2->A[j];
    arr3->length = k;
    arr3->size = 10;
    return arr3;
}

struct Array *Intersection(struct Array *arr1, struct Array *arr2)
{
    int i, j, k;
    i = j = k = 0;
    //add if  both are same, present in both
    struct Array *arr3 = (struct Array *)malloc(sizeof(struct Array));
    while (i < arr1->length && j < arr2->length)
    {
        if (arr1->A[i] < arr2->A[j])
            i++;
        else if (arr2->A[j] < arr1->A[i])
            j++;
        else if (arr1->A[i] == arr2->A[j])
        {
            arr3->A[k++] = arr1->A[i++];
            j++;
        }
    }
    arr3->length = k;
    arr3->size = 10;
    return arr3;
}

struct Array *Difference(struct Array *arr1, struct Array *arr2)
{
    int i, j, k;
    i = j = k = 0;
    //a-b=c
    struct Array *arr3 = (struct Array *)malloc(sizeof(struct Array));
    while (i < arr1->length && j < arr2->length)
    {
        //if a<b then a is already crossed or not present hence add it
        if (arr1->A[i] < arr2->A[j])
            arr3->A[k++] = arr1->A[i++];
        else if (arr2->A[j] < arr1->A[i])
            j++;
        else
        {
            i++;
            j++;
        }
    }
    for (; i < arr1->length; i++)
        arr3->A[k++] = arr1->A[i];
    arr3->length = k;
    arr3->size = 10;
    return arr3;
}

int main()
{
    struct Array arr1 = {{2, 9, 21, 28, 35}, 10, 5};
    struct Array arr2 = {{2, 3, 9, 18, 28}, 10, 5};
    Display(arr1);
    Display(arr2);
    struct Array *arr3;
    arr3 = Union(&arr1, &arr2);
    Display(*arr3);
    arr3 = Intersection(&arr1, &arr2);
    Display(*arr3);
    arr3 = Difference(&arr1, &arr2);
    Display(*arr3);
    return 0;
}

Conclusion

This post [Performing Set Operations on Arrays] is a part of my #30DaysChallenge to write a blog post every day on what I learn daily, All the Best~ Abhiram Reddy.

Leave a Reply

Your email address will not be published. Required fields are marked *

Popular posts