This document presents a C++ program to find the union and intersection of two arrays using hashing techniques. The program utilizes the C++ Standard Template Library (STL) to leverage the unordered_set for efficient insertion and lookup operations.

Program Structure

• Include necessary headers: The program includes the iostream and unordered_set headers for input-output operations and using hash tables, respectively.
• Function Definitions: The program defines two functions: findUnion and findIntersection, each taking two arrays and their sizes as input.
• Main Function: In the main function, two arrays are defined, and the union and intersection of these arrays are computed and displayed.

Program Code

#include <iostream>
#include <unordered_set>

using namespace std;

/**
 * Function to find the union of two arrays.
 * @param arr1: First array
 * @param size1: Size of the first array
 * @param arr2: Second array
 * @param size2: Size of the second array
 * @return: A set containing the union of the two arrays
 */
unordered_set findUnion(int arr1[], int size1, int arr2[], int size2) {
    unordered_set unionSet;

    // Insert elements of first array into the set
    for (int i = 0; i < size1; i++) {
        unionSet.insert(arr1[i]);
    }

    // Insert elements of second array into the set
    for (int i = 0; i < size2; i++) {
        unionSet.insert(arr2[i]);
    }

    return unionSet;
}

/**
 * Function to find the intersection of two arrays.
 * @param arr1: First array
 * @param size1: Size of the first array
 * @param arr2: Second array
 * @param size2: Size of the second array
 * @return: A set containing the intersection of the two arrays
 */
unordered_set findIntersection(int arr1[], int size1, int arr2[], int size2) {
    unordered_set intersectionSet;
    unordered_set elementsSet;

    // Store elements of the first array in a set
    for (int i = 0; i < size1; i++) {
        elementsSet.insert(arr1[i]);
    }

    // Check for intersection with the second array
    for (int i = 0; i < size2; i++) {
        if (elementsSet.find(arr2[i]) != elementsSet.end()) {
            intersectionSet.insert(arr2[i]);
        }
    }

    return intersectionSet;
}

int main() {
    int arr1[] = {1, 2, 3, 4, 5};
    int arr2[] = {4, 5, 6, 7, 8};

    int size1 = sizeof(arr1) / sizeof(arr1[0]);
    int size2 = sizeof(arr2) / sizeof(arr2[0]);

    unordered_set unionSet = findUnion(arr1, size1, arr2, size2);
    unordered_set intersectionSet = findIntersection(arr1, size1, arr2, size2);

    // Displaying the union
    cout << "Union of the two arrays: ";
    for (int x : unionSet) {
        cout << x << " ";
    }
    cout << endl;

    // Displaying the intersection
    cout << "Intersection of the two arrays: ";
    for (int x : intersectionSet) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

Explanation of the Program

The program is structured as follows:

1. Include Directives:The program begins by including the necessary header files for input-output and data structures. The unordered_set is used to store unique elements and provides efficient operations for union and intersection.
2. findUnion Function:This function takes two arrays and their sizes as parameters. It inserts all elements of both arrays into an unordered_set, effectively calculating the union of the two arrays. Since sets automatically handle duplicates, only unique elements are stored.
3. findIntersection Function:This function also takes two arrays and their sizes. It first stores all elements of the first array in a set, then checks each element of the second array against this set. If an element from the second array is found in the set, it is added to the intersection set.
4. Main Function:In the main function, two sample arrays are defined. The size of each array is computed using the sizeof operator. The findUnion and findIntersection functions are then called, and the results are printed to the console.

Conclusion

This program demonstrates an efficient method to compute the union and intersection of two arrays using hashing techniques in C++. By utilizing the unordered_set from the STL, we ensure optimal time complexity for insertions and lookups, making this approach both effective and straightforward.