Example: Find Missing Elements using Sorting and Iteration in C

// Find Missing Elements using Sorting and Iteration
#include <stdio.h>
#include <stdlib.h> // For qsort

// Comparison function for qsort
int compareIntegers(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

// Function to find missing elements using sorting
void findMissingWithSorting(int arr[], int n, int min_val, int max_val) {
    // Step 1: Sort the input array
    qsort(arr, n, sizeof(int), compareIntegers);

    printf("Missing elements in range [%d, %d]: ", min_val, max_val);
    bool found_missing = false;
    int expected_num = min_val;
    int arr_idx = 0;

    // Step 2: Iterate through the sorted array and the expected range
    while (expected_num <= max_val) {
        // Skip elements in arr that are outside the desired range or duplicates
        while (arr_idx < n && arr[arr_idx] < expected_num) {
            arr_idx++;
        }
        
        // If the current expected_num is not found in arr
        // (either arr_idx reached end, or arr[arr_idx] is greater than expected_num)
        if (arr_idx >= n || arr[arr_idx] > expected_num) {
            printf("%d ", expected_num);
            found_missing = true;
        } else { // arr[arr_idx] == expected_num
            // Current expected_num is present, move to the next unique element in arr
            // and the next expected_num
            arr_idx++; // Move to next element in array
        }
        expected_num++; // Always move to the next expected number in range
    }
    
    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
    findMissingWithSorting(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;
    findMissingWithSorting(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;
    findMissingWithSorting(arr3, n3, min_val3, max_val3);
    
    int arr4[] = {1, 1, 3, 5, 5}; // Test with duplicates
    int n4 = sizeof(arr4) / sizeof(arr4[0]);
    int min_val4 = 1;
    int max_val4 = 5;
    findMissingWithSorting(arr4, n4, min_val4, max_val4);

    return 0;
}