Find Duplicate in Range 0 and n-1

Code

#include <stdio.h>

int find_duplicate(int arr[], int n) {
    // Your logic here

    // Brute force (O(n^2))

    // int start = 0;
    // int index = 0;
    // int end = n;
    // while(start<end)
    // {
    //     index=start+1;
    //     while(index<end)
    //     {
    //         if(arr[start]==arr[index])
    //         {
    //             return arr[index];
    //         }
    //         index++;
    //     }
        
    //     start++;
    // }
    // return -1;
    
    //Tortoise and rabbit (O(n))
    int slow = arr[0]+1;
    int fast = arr[0]+1;

    // Phase 1: Find meeting point inside cycle
    do {
        slow = arr[slow]+1;          // move one step
        fast = arr[arr[fast]+1]+1;     // move two steps
    } while (slow != fast);

    // Phase 2: Find cycle entry = duplicate number
    slow = arr[0]+1;
    while (slow != fast) {
        slow = arr[slow]+1;
        fast = arr[fast]+1;
    }

    return slow-1; // or fast


    // Pigeonhole Principle/ Binary (O(nlogn))

}

int main() {
    int n;
    scanf("%d", &n);

    int arr[100];
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);

    int result = find_duplicate(arr, n);
    printf("%d", result);
    return 0;
}

Solving Approach