human
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"
How can the above be solved in Python?
assistant
#Here is code to find duplicate in an array in O ( n ) and by using O ( 1 ) extra space and the other steps required.
 def findDuplicate ( arr ) :
	slow = arr [ 0 ]
	fast = arr [ 0 ]
	while True :
		slow = arr [ slow ]
		fast = arr [ arr [ fast ] ]
		if slow == fast :
			break
	ptr1 = arr [ 0 ]
	ptr2 = slow
	while ptr1 != ptr2 :
		ptr1 = arr [ ptr1 ]
		ptr2 = arr [ ptr2 ]
	return ptr1
if __name__ == ' _ _ main _ _ ' :
	arr = [ 1 , 3 , 2 , 1 ]
	print ( findDuplicate ( arr ) )