Find the duplicate number in an array of n+1 integers in the range 1..n.
#include <stddef.h>
/* Floyd's cycle detection: O(n) time, O(1) space, array not modified */
int find_duplicate(const int *a, size_t n_plus_1)
{
(void)n_plus_1;
int slow = a[0], fast = a[a[0]];
while (slow != fast) { /* phase 1: meet inside the cycle */
slow = a[slow];
fast = a[a[fast]];
}
slow = 0; /* phase 2: find the cycle entrance */
while (slow != fast) {
slow = a[slow];
fast = a[fast];
}
return slow;
}
/* {1, 3, 4, 2, 2} -> 2 */
Points: treat values as "next" pointers (i → a[i]); a duplicate value means two indexes point to the same node, which creates a cycle whose entrance is the duplicate. This is the linked-list loop algorithm on an array. Simpler alternatives: a seen-bitmap (O(n) memory), sorting (modifies the array), or marking visited indexes by negating values (modifies the array).