Find the Duplicate Number

 https://leetcode.com/problems/find-the-duplicate-number/

//naive approach is o(nlogn) where you need to first sort the array then arr[i]==arr[i+1] then return that arr[i]
// o(n) approach : take a freq array where the array is of size n and all initialized to 0 while traversing we go to the arr[i ] and make it 1 if already 1 is there then we have to return arr[i]

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

int n=nums.size();
        int ans=0;
        vector<int>freq(n+2,0);
        for(int i=0;i<n;i++){
            if(freq[nums[i]]==1){
                ans= nums[i];
                break;
            }
            else{
                freq[nums[i]]=1;
            }
        }

 return ans;