Find Duplicate Cycle Detection Floyd cycle-detection-Floyd.cpp

cycle-detection-Floyd.cpp

//1,3,4,2,2
[1,2,3,4]
4/2 = 2
int findDuplicate(vector<int>_&nums) {
	
       int low = 1;

       int high = nums.size() - 1;// 5= 5-1= 4

       [1,2,3,4]


       while(low < high) {

            int mid = (low + high) / 2;

            int count = 0;

            for(int num: nums) {

                if(num <= mid) {

                      count++;
                }
            }      

            if(count > mid) high = mid;

                     else 

                           low = mid + 1;
       } 

       return low;

}

//1,3,4,2,2

int findDuplicate(vector<int>_&nums) {

            int slow = nums[ 0 ]; //1

            int fast = nums[ 0 ]; //1

            do {
                   slow = nums[ slow ];  //1

                   fast = nums[ nums[ fast ] ] ;//nums[3];//

            } while( slow != fast );

            fast = nums[0];

            while(slow != fast) {

               slow = nums[slow];

               fast = nums[fast];
            }

            return fast;
}