LeetCode Hot 100 P287 Find the Duplicate Number

---

Timeline

Timeline

2026-03-17

init

Two pointers, pigeonhole principle, Floyd's cycle detection (Floyd's tortoise and hare)

---

Problem:

P287 Find the Duplicate Number

https://leetcode.cn/problems/find-the-duplicate-number/description/?envType=study-plan-v2&envId=top-100-liked

The pigeonhole principle (also called the drawer principle, in English Pigeonhole Principle) is a very basic but powerful principle in combinatorics.

Basic idea: If n + 1 pigeons are placed into n pigeonholes, then at least one pigeonhole contains ≥2 pigeons.

This problem uses Floyd’s cycle detection to convert it into a problem like P142.

P142 Linked List Cycle II

https://even629.com/posts/142

#include <vector>
using std::vector;

class Solution {
    public:
        int findDuplicate(vector<int> &nums)
        {
                // 1 <= n <= 105
                // nums.length == n + 1
                // 1 <= nums[i] <= n
                // In nums, only one integer appears two or more times, and all other integers appear only once.

                int slow = 0, fast = 0;

                do {
                        slow = nums[slow];
                        fast = nums[nums[fast]];
                } while (slow != fast);
                // Meet
                slow = 0;
                do {
                        slow = nums[slow];
                        fast = nums[fast];
                } while (slow != fast);

                return slow;
        }
};