Find duplicate in an array in O ( n ) and by using O ( 1 ) extra space | CPP 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
#include <iostream> NEW_LINE using namespace std ; 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 ; } int main ( ) { int arr [ ] = { 1 , 3 , 2 , 1 } ; cout << findDuplicate ( arr ) << endl ; return 0 ; }