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
< ? php function findDuplicate ( & $ arr ) { $ slow = $ arr [ 0 ] ; $ fast = $ arr [ 0 ] ; do { $ slow = $ arr [ $ slow ] ; $ fast = $ arr [ $ arr [ $ fast ] ] ; } while ( $ slow != $ fast ) ; $ ptr1 = $ arr [ 0 ] ; $ ptr2 = $ slow ; while ( $ ptr1 != $ ptr2 ) { $ ptr1 = $ arr [ $ ptr1 ] ; $ ptr2 = $ arr [ $ ptr2 ] ; } return $ ptr1 ; } $ arr = array ( 1 , 3 , 2 , 1 ) ; echo " ▁ " . findDuplicate ( $ arr ) ; ? >