class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        
        int slow = nums[0];
        int fast = nums[0];
        do{
            slow = nums[slow];
            fast = nums[nums[fast]];
        }while(slow != fast);
        
        slow = nums[0];
        int ans = fast;
        while(fast != slow){
            fast = nums[fast];
            slow = nums[slow];
            ans = slow;
        }
        
        return ans;
    }
};