Find Duplicate in Range 0 and n-1

Code

#include <stdio.h>

int find_duplicate(int arr[], int n) {
    // Dùng long long để tránh bị tràn số khi n lớn
    long long sum_idx = 0;
    long long sum_sq_idx = 0;
    long long sum_arr = 0;
    long long sum_sq_arr = 0;

    for (int i = 0; i < n; i++) {
        // Tính tổng cho các chỉ số (0 đến n-1)
        sum_idx += i;
        sum_sq_idx += (long long)i * i;

        // Tính tổng cho các giá trị trong mảng
        sum_arr += arr[i];
        sum_sq_arr += (long long)arr[i] * arr[i];
    }

    // 1. R - M = diff_sum
    long long diff_sum = sum_arr - sum_idx;

    // 2. R^2 - M^2 = diff_sq
    long long diff_sq = sum_sq_arr - sum_sq_idx;

    // 3. R + M = diff_sq / diff_sum
    // (Phải kiểm tra diff_sum != 0, nhưng trong bài này nó luôn khác 0
    // vì R != M)
    long long sum_R_M = diff_sq / diff_sum;

    // 4. Giải hệ:
    // R - M = diff_sum
    // R + M = sum_R_M
    // => 2R = diff_sum + sum_R_M
    long long R = (diff_sum + sum_R_M) / 2;

    return (int)R;
}

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