Example: Detect Duplicates Using Pigeonholes in C

// Detect Duplicates Using Pigeonholes
#include <stdio.h>
#include <stdbool.h>
#include <limits.h> // For INT_MAX/INT_MIN if needed, though not strictly for this example

// Function to find a duplicate in an array with elements in range [min_val, max_val]
int find_duplicate(int arr[], int n, int min_val, int max_val) {
    if (n <= 1) { // No duplicates possible in empty or single-element array
        return -1; // Indicate no duplicate
    }

    // Calculate the number of possible unique values (pigeonholes)
    int range_size = max_val - min_val + 1;

    // The pigeonhole principle applies if n > range_size
    if (n <= range_size) {
        // If number of items <= number of pigeonholes, duplicates are not guaranteed
        // A more general duplicate check (e.g., sorting, hashing) would be needed
        // For this specific problem, we assume n > range_size
        printf("Note: Pigeonhole Principle guarantees a duplicate only if N > (Max - Min + 1).\n");
        printf("Current N: %d, Range Size: %d\n", n, range_size);
        // Fall through to check anyway, as a duplicate might still exist.
    }

    // Create a boolean array to mark if a value has been seen.
    // Size is `range_size + 1` to use 1-based indexing for values or handle 0 correctly.
    // For values from `min_val` to `max_val`, map them to indices `0` to `range_size - 1`.
    bool *seen = (bool *)calloc(range_size, sizeof(bool)); // Initialize all to false

    if (seen == NULL) {
        printf("Memory allocation failed!\n");
        return -1;
    }

    for (int i = 0; i < n; i++) {
        int val = arr[i];
        if (val < min_val || val > max_val) {
            printf("Error: Value %d out of expected range [%d, %d]\n", val, min_val, max_val);
            free(seen);
            return -1;
        }

        // Map the value to an index in the 'seen' array
        int index = val - min_val;

        if (seen[index]) {
            free(seen);
            return val; // Duplicate found
        }
        seen[index] = true; // Mark as seen
    }

    free(seen);
    return -1; // No duplicate found (shouldn't happen if n > range_size)
}

int main() {
    int numbers1[] = {10, 2, 8, 5, 2, 7, 3, 10, 1}; // 9 numbers, range 1-10
    int n1 = sizeof(numbers1) / sizeof(numbers1[0]);
    int min1 = 1, max1 = 10; // Range of values

    printf("Array 1: ");
    for(int i=0; i<n1; ++i) printf("%d ", numbers1[i]);
    printf("\n");
    int duplicate1 = find_duplicate(numbers1, n1, min1, max1);
    if (duplicate1 != -1) {
        printf("Duplicate found in Array 1: %d\n", duplicate1);
    } else {
        printf("No duplicate found in Array 1.\n");
    }
    printf("\n");

    int numbers2[] = {5, 3, 8, 1, 4, 9, 2, 7, 6}; // 9 numbers, range 1-9
    int n2 = sizeof(numbers2) / sizeof(numbers2[0]);
    int min2 = 1, max2 = 9; // Range of values
    
    printf("Array 2: ");
    for(int i=0; i<n2; ++i) printf("%d ", numbers2[i]);
    printf("\n");
    int duplicate2 = find_duplicate(numbers2, n2, min2, max2);
    if (duplicate2 != -1) {
        printf("Duplicate found in Array 2: %d\n", duplicate2);
    } else {
        printf("No duplicate found in Array 2.\n");
    }
    printf("\n");

    int numbers3[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1}; // 11 numbers, range 1-10
    int n3 = sizeof(numbers3) / sizeof(numbers3[0]);
    int min3 = 1, max3 = 10; // Range of values

    printf("Array 3: ");
    for(int i=0; i<n3; ++i) printf("%d ", numbers3[i]);
    printf("\n");
    int duplicate3 = find_duplicate(numbers3, n3, min3, max3);
    if (duplicate3 != -1) {
        printf("Duplicate found in Array 3: %d\n", duplicate3);
    } else {
        printf("No duplicate found in Array 3.\n");
    }
    printf("\n");

    return 0;
}