Example: Pigeonhole Principle Duplicate Finder in C++

// Pigeonhole Principle Duplicate Finder
    #include <iostream>
    #include <vector>
    #include <numeric>

    int findDuplicatePigeonhole(const std::vector<int>& nums) {
        // Step 1: Determine the range of numbers. Given numbers are [1, n-1].
        // So, we need 'n' pigeonholes (from index 0 to n-1 or 1 to n-1, adjusted).
        // If numbers are 1 to max_val, we need a boolean array of size max_val + 1.
        // For problem: n numbers in range [1, n-1]. The size of array is nums.size().
        // Max value is nums.size() - 1. So, array of size nums.size().
        std::vector<bool> seen(nums.size(), false); // Pigeonholes initialized to empty

        // Step 2: Iterate through the input numbers (pigeons)
        for (int num : nums) {
            // Step 3: Check if this pigeonhole (index 'num') is already occupied
            if (seen[num]) {
                // Step 4: If it's occupied, we found a duplicate
                return num;
            }
            // Step 5: Mark this pigeonhole as occupied
            seen[num] = true;
        }
        // Step 6: This line should ideally not be reached given problem constraints
        return -1;
    }

    int main() {
        std::vector<int> nums = {1, 3, 4, 2, 2}; // n=5, range [1,4]. Max val 4. Seen size 5.
        int duplicate = findDuplicatePigeonhole(nums);

        if (duplicate != -1) {
            std::cout << "The duplicate number is: " << duplicate << std::endl;
        } else {
            std::cout << "No duplicate found." << std::endl;
        }

        std::vector<int> nums2 = {3, 1, 3, 4, 2}; // n=5, range [1,4]
        duplicate = findDuplicatePigeonhole(nums2);
        if (duplicate != -1) {
            std::cout << "The duplicate number is: " << duplicate << std::endl;
        } else {
            std::cout << "No duplicate found." << std::endl;
        }

        return 0;
    }