Find The Duplicate Number

Given an unsorted array of positive numbers, nums, such that the values lie in the range [1,n], inclusive, and that there are

Given an unsorted array of positive numbers, nums, such that the values lie in the range [1,n], inclusive, and that there are n+1 numbers in the array, find and return the duplicate number present in nums. There is only one repeated number in nums.

Note

You cannot modify the given array nums. You have to solve the problem using only constant extra space.

Constraints

• 1 ≤ n ≤ 10³
• nums.length = n + 1
• 1 ≤ nums[i] ≤ n
• All the integers in nums are unique except for one integer that will appear more than once.

Solution

We can use the slow and fast pointer method to find the duplicate number.

• The fast pointer moves through the array at two times the speed of the slow pointer.
• When the fast and slow pointers meet, we reset the slow pointer back to the start (head).
• Now, we move both pointers at the same speed.
• The next point where they meet is the start of the cycle. This is also our duplicate number.

Code

function findDuplicate(nums) {
  let fast = nums[0];
  let slow = nums[0];

  while (true) {
    slow = nums[slow];
    fast = nums[nums[fast]];
    if (slow == fast) {
      break;
    }
  }

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

  return fast;
}