Find duplicate in an array in O ( n ) and by using O ( 1 ) extra space | Java code to find the repeated elements in the array where every other is present once ; Function to find duplicate ; Find the intersection point of the slow and fast . ; Find the " entrance " to the cycle . ; Driver Code
import java . util . * ; class GFG { public static int findDuplicate ( int [ ] arr ) { int slow = arr [ 0 ] ; int fast = arr [ 0 ] ; do { slow = arr [ slow ] ; fast = arr [ arr [ fast ] ] ; } while ( slow != fast ) ; int ptr1 = arr [ 0 ] ; int ptr2 = slow ; while ( ptr1 != ptr2 ) { ptr1 = arr [ ptr1 ] ; ptr2 = arr [ ptr2 ] ; } return ptr1 ; } public static void main ( String [ ] args ) { int [ ] arr = { 1 , 3 , 2 , 1 } ; System . out . println ( " " + findDuplicate ( arr ) ) ; System . exit ( 0 ) ; } }