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 <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

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))
        printf("Arrays are disjoint\n");
    else
        printf("Arrays are not disjoint\n");
    return 0;
}
            

Method 2: Using Hashing

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

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define MAX 1000

bool areDisjoint(int arr1[], int n1, int arr2[], int n2) {
    bool hash[MAX] = {false};
    for (int i = 0; i < n1; i++)
        hash[arr1[i]] = true;
    for (int j = 0; j < n2; j++) {
        if (hash[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))
        printf("Arrays are disjoint\n");
    else
        printf("Arrays are not disjoint\n");
    return 0;
}
            

Method 3: Using Sorting and Binary Search

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

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

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

bool binarySearch(int arr[], int size, int key) {
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == key) return true;
        else if (arr[mid] < key) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

bool areDisjoint(int arr1[], int n1, int arr2[], int n2) {
    qsort(arr1, n1, sizeof(int), compare);
    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))
        printf("Arrays are disjoint\n");
    else
        printf("Arrays are not disjoint\n");
    return 0;
}