Finding Arrays are Disjoint or Not in C++

Understanding Disjoint Arrays

Two arrays are said to be disjoint if they have no elements in common.

We will explore three different methods to check if two arrays are disjoint in C++.

Method 1: Using Nested Loops

This method iterates through both arrays and checks for common elements.

#include <iostream>
#include <algorithm>
using namespace std;

bool areDisjoint(int arr1[], int n1, int arr2[], int n2) {
    for (int i = 0; i < n1; i++) {
        for (int j = 0; j < n2; j++) {
            if (arr1[i] == arr2[j]) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    int arr1[] = {1, 2, 3, 4};
    int arr2[] = {5, 6, 7, 8};
    if (areDisjoint(arr1, 4, arr2, 4))
        cout << "Arrays are disjoint" << endl;
    else
        cout << "Arrays are not disjoint" << endl;
    return 0;
}
            

Method 2: Using Hashing

This method uses a hash set to check for common elements efficiently.

#include <iostream>
#include <algorithm>
#include <unordered_set>
using namespace std;

bool areDisjoint(int arr1[], int n1, int arr2[], int n2) {
    unordered_set hash;
    for (int i = 0; i < n1; i++)
        hash.insert(arr1[i]);
    for (int j = 0; j < n2; j++) {
        if (hash.find(arr2[j]) != hash.end())
            return false;
    }
    return true;
}

int main() {
    int arr1[] = {1, 2, 3, 4};
    int arr2[] = {5, 6, 7, 8};
    if (areDisjoint(arr1, 4, arr2, 4))
        cout << "Arrays are disjoint" << endl;
    else
        cout << "Arrays are not disjoint" << endl;
    return 0;
}
            

Method 3: Using Sorting and Binary Search

This method sorts one array and uses binary search to check for common elements.

#include <iostream>
#include <algorithm>
using namespace std;

bool binarySearch(int arr[], int size, int key) {
    return binary_search(arr, arr + size, key);
}

bool areDisjoint(int arr1[], int n1, int arr2[], int n2) {
    sort(arr1, arr1 + n1);
    for (int i = 0; i < n2; i++) {
        if (binarySearch(arr1, n1, arr2[i]))
            return false;
    }
    return true;
}

int main() {
    int arr1[] = {1, 2, 3, 4};
    int arr2[] = {5, 6, 7, 8};
    if (areDisjoint(arr1, 4, arr2, 4))
        cout << "Arrays are disjoint" << endl;
    else
        cout << "Arrays are not disjoint" << endl;
    return 0;
}