Advertisement
whitesurge

Tortoise and the hare

Feb 28th, 2020
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. function findDuplicate(nums){
  2.   let tortoise = nums[0]
  3.   let hare = nums[0]
  4.   while(true){
  5.     tortoise = nums[tortoise]
  6.     hare = nums[nums[hare]]
  7.     if(tortoise == hare){
  8.       break
  9.     }
  10.   }
  11.   let ptr1 = nums[0]
  12.   let ptr2 = tortoise
  13.   while (ptr1 != ptr2){
  14.     ptr1 = nums[ptr1]
  15.     ptr2 = nums[ptr2]
  16.   }
  17.   return ptr1
  18. }
  19. console.log(findDuplicate([2,1,3,4,1]))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement