Find Duplicate in Range 0 and n-1

Time complexity O(n) - Space complexity O(1)

#include <stdio.h>

int find_duplicate(int arr[], int n) {
    int duplicate_pos = -1;
    int internal_sum = 0, actual_sum = 0;

    for (int i=0; i<n; i++) {
        internal_sum += i;
        actual_sum += arr[i];
    }

    if (actual_sum > internal_sum) {
        duplicate_pos = actual_sum - internal_sum;
        return duplicate_pos;
    } 
    else {
        duplicate_pos = internal_sum - actual_sum;
        return arr[duplicate_pos];
    }

    
    
}

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:

1. Calculate two sums:

   • internal_sum: Sum of numbers from 0 to n-1 (using formula or iteration)

   • actual_sum: Sum of all elements in the array

2. Determine the duplicate:

   • If actual_sum > internal_sum: The duplicate is the difference between sums

   • If actual_sum < internal_sum: The duplicate is the array element at the index equal to the difference (since the missing number creates an offset)