Find duplicate in an array in O ( n ) and by using O ( 1 ) extra space | Function to find duplicate ; Find the intersection point of the slow and fast . ; Find the " entrance " to the cycle . ; Driver code
function findDuplicate ( arr ) { let slow = arr [ 0 ] ; let fast = arr [ 0 ] ; do { slow = arr [ slow ] ; fast = arr [ arr [ fast ] ] ; } while ( slow != fast ) ; let ptr1 = arr [ 0 ] ; let ptr2 = slow ; while ( ptr1 != ptr2 ) { ptr1 = arr [ ptr1 ] ; ptr2 = arr [ ptr2 ] ; } return ptr1 ; } let arr = [ 1 , 3 , 2 , 1 ] ; document . write ( findDuplicate ( arr ) + " " ) ;