Example: Pigeonhole Duplicate Example in C

// Pigeonhole Duplicate Example
#include <stdio.h>
#include <stdbool.h> // For boolean type

int main() {
    // Step 1: Define the array of numbers
    int numbers[] = {3, 1, 4, 1, 2};
    int n = sizeof(numbers) / sizeof(numbers[0]); // Number of elements

    // Step 2: Define the range of possible values (pigeonholes)
    // Numbers are between 1 and 4. We need an array of size 5 to use indices 1-4.
    bool seen[5] = {false}; // Initialize all to false. Index 0 is unused.

    printf("Numbers in array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", numbers[i]);
    }
    printf("\n");

    // Step 3: Iterate through the numbers and mark them as seen
    printf("Checking for duplicates...\n");
    for (int i = 0; i < n; i++) {
        int current_number = numbers[i];
        if (seen[current_number]) { // If this number has been seen before
            printf("Duplicate found: %d\n", current_number);
            return 0; // Exit after finding the first duplicate
        }
        seen[current_number] = true; // Mark this number as seen
    }

    printf("No duplicates found (this case should not happen given the problem setup).\n");
    return 0;
}