287_Find_the_Duplicate_Number.java

/*
287. Find the Duplicate Number
Difficulty: Medium

287_Find_the_Duplicate_Number.java
*/

class Solution {
  public int findDuplicate(int[] nums) {
    
    int slow = nums[nums[0]];
    int fast = nums[nums[nums[0]]];

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

    slow = nums[0];

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

    return slow;
    
  }
}