Example: Disjoint Arrays - Frequency Array in C

// Disjoint Arrays - Frequency Array
#include <stdio.h>
#include <stdbool.h>
#include <string.h> // For memset

#define MAX_VAL 1001 // Assuming array elements are between 0 and 1000

// Function to check if two arrays are disjoint using a frequency array
bool areArraysDisjoint_FrequencyArray(int arr1[], int n1, int arr2[], int n2) {
    // Step 1: Create a boolean frequency array and initialize to false
    // 'seen[x]' will be true if 'x' is present in arr1
    bool seen[MAX_VAL];
    memset(seen, false, sizeof(seen)); // Initialize all to false

    // Step 2: Populate the 'seen' array with elements from arr1
    for (int i = 0; i < n1; i++) {
        // Check if element is within assumed range
        if (arr1[i] >= 0 && arr1[i] < MAX_VAL) {
            seen[arr1[i]] = true;
        } else {
            // Handle elements out of range or return false if necessary
            // For simplicity, we'll ignore out-of-range elements for this example,
            // but in a real scenario, you'd handle this.
        }
    }

    // Step 3: Iterate through arr2 and check against the 'seen' array
    for (int i = 0; i < n2; i++) {
        // Check if element is within assumed range and was seen in arr1
        if (arr2[i] >= 0 && arr2[i] < MAX_VAL && seen[arr2[i]]) {
            return false; // Found a common element
        }
        // If element is out of range, this approach might miss commonalities
        // if the corresponding element in arr1 was also out of range.
        // For production, ensure MAX_VAL covers all possible values.
    }
    // Step 4: If no common elements were found
    return true; // Arrays are disjoint
}

int main() {
    int arr1_a[] = {1, 2, 3, 4};
    int n1_a = sizeof(arr1_a) / sizeof(arr1_a[0]);
    int arr2_a[] = {5, 6, 7};
    int n2_a = sizeof(arr2_a) / sizeof(arr2_a[0]);

    printf("Arrays 1A and 2A (freq array): ");
    if (areArraysDisjoint_FrequencyArray(arr1_a, n1_a, arr2_a, n2_a)) {
        printf("Disjoint\n");
    } else {
        printf("Not Disjoint\n");
    }

    int arr1_b[] = {10, 20, 30};
    int n1_b = sizeof(arr1_b) / sizeof(arr1_b[0]);
    int arr2_b[] = {20, 40, 50};
    int n2_b = sizeof(arr2_b) / sizeof(arr2_b[0]);

    printf("Arrays 1B and 2B (freq array): ");
    if (areArraysDisjoint_FrequencyArray(arr1_b, n1_b, arr2_b, n2_b)) {
        printf("Disjoint\n");
    } else {
        printf("Not Disjoint\n");
    }

    int arr1_c[] = {990, 10, 500};
    int n1_c = sizeof(arr1_c) / sizeof(arr1_c[0]);
    int arr2_c[] = {10, 20, 30};
    int n2_c = sizeof(arr2_c) / sizeof(arr2_c[0]);

    printf("Arrays 1C and 2C (freq array): ");
    if (areArraysDisjoint_FrequencyArray(arr1_c, n1_c, arr2_c, n2_c)) {
        printf("Disjoint\n");
    } else {
        printf("Not Disjoint\n");
    }

    return 0;
}