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
def findDuplicate ( arr ) : NEW_LINE INDENT slow = arr [ 0 ] NEW_LINE fast = arr [ 0 ] NEW_LINE while True : NEW_LINE INDENT slow = arr [ slow ] NEW_LINE fast = arr [ arr [ fast ] ] NEW_LINE if slow == fast : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT ptr1 = arr [ 0 ] NEW_LINE ptr2 = slow NEW_LINE while ptr1 != ptr2 : NEW_LINE INDENT ptr1 = arr [ ptr1 ] NEW_LINE ptr2 = arr [ ptr2 ] NEW_LINE DEDENT return ptr1 NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 3 , 2 , 1 ] NEW_LINE print ( findDuplicate ( arr ) ) NEW_LINE DEDENT