#5
Fast & Slow Pointers
Fast & Slow Pointers (Floyd's)An array of n + 1 integers has each value in the range 1..n; exactly one value repeats. Find it using O(1) extra space without modifying the array.
function findDuplicate(nums: number[]): number {
let slow = nums[0], fast = nums[0];
do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow !== fast);
slow = nums[0];
while (slow !== fast) { slow = nums[slow]; fast = nums[fast]; }
return slow;
}def find_duplicate(nums)
slow = fast = nums[0]
loop do
slow = nums[slow]
fast = nums[nums[fast]]
break if slow == fast
end
slow = nums[0]
while slow != fast
slow = nums[slow]
fast = nums[fast]
end
slow
end