Find_Duplicate_in_array.cpp

#include <bits/stdc++.h>

int findDuplicate(vector<int> &arr, int n)
{
    // Write your code here.
    int slow = arr[0];
    int fast = arr[0];

    do
    {
        slow = arr[slow];
        fast = arr[arr[fast]];
    } while (slow != fast);

    fast = arr[0];

    while (fast != slow)
    {
        fast = arr[fast];
        slow = arr[slow];
    }

    return fast;
}