Given an array of size n+1 having all the numbers between 1 to n, find the duplicate number without using extra space. We are not allowed to modify the array.
a = [1, 2, 3, 4, 5, 1] ans = 1
Do we remember the hare and the tortoise algorithm to find the loop in a linked list.
The same algorithm can be used here to find the duplicate element.
Imagine the numbers finding a linked list such that:
1. index i points to the element at a[i]
In this case, if there is a duplicate number, then it'll start the loop.