Sep19 2023 - Find-the-duplicate-number

[Nabil-Salah]

Description

https://leetcode.com/problems/find-the-duplicate-number/?envType=daily-question&envId=2023-09-19

Code of Conduct

• I follow Contributing Guidelines of this project.

[crazyGru]

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);

        int tortoise = nums[0];
        int hare = nums[0];

        // Phase 1: Find the intersection point of the two pointers
        do {
            tortoise = nums[tortoise];
            hare = nums[nums[hare]];
        } while (tortoise != hare);

        // Phase 2: Find the entrance of the cycle
        tortoise = nums[0];
        while (tortoise != hare) {
            tortoise = nums[tortoise];
            hare = nums[hare];
        }

        return hare;
    }
};