Example: Find Missing Elements using Frequency Array in C

// Find Missing Elements using Frequency Array
#include <stdio.h>
#include <stdbool.h> // For bool type

// Function to find missing elements using a frequency array
void findMissingWithFrequencyArray(int arr[], int n, int min_val, int max_val) {
    // Determine the size of the frequency array
    int range_size = max_val - min_val + 1;
    bool present[range_size];

    // Initialize all elements in the present array to false
    for (int i = 0; i < range_size; i++) {
        present[i] = false;
    }

    // Mark the elements that are present in the input array
    for (int i = 0; i < n; i++) {
        if (arr[i] >= min_val && arr[i] <= max_val) {
            present[arr[i] - min_val] = true;
        }
    }

    printf("Missing elements in range [%d, %d]: ", min_val, max_val);
    bool found_missing = false;
    // Iterate through the present array to find missing elements
    for (int i = 0; i < range_size; i++) {
        if (!present[i]) {
            printf("%d ", i + min_val);
            found_missing = true;
        }
    }
    if (!found_missing) {
        printf("None");
    }
    printf("\n");
}

int main() {
    // Step 1: Define the input array and its size
    int arr[] = {1, 3, 5, 6, 8, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Step 2: Define the minimum and maximum values of the expected range
    int min_val = 1;
    int max_val = 10;

    // Step 3: Call the function to find and print missing elements
    findMissingWithFrequencyArray(arr, n, min_val, max_val);

    int arr2[] = {2, 4, 6, 8};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    int min_val2 = 1;
    int max_val2 = 10;
    findMissingWithFrequencyArray(arr2, n2, min_val2, max_val2);

    int arr3[] = {1, 2, 3, 4, 5};
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
    int min_val3 = 1;
    int max_val3 = 5;
    findMissingWithFrequencyArray(arr3, n3, min_val3, max_val3);
    
    return 0;
}