Example: Find Single Missing Element using Summation in C

// Find Single Missing Element using Summation
#include <stdio.h>

// Function to find a single missing element using summation
int findSingleMissingWithSummation(int arr[], int n, int min_val, int max_val) {
    long long expected_sum = 0;
    long long actual_sum = 0;

    // Step 1: Calculate the expected sum of numbers from min_val to max_val
    // This handles ranges not starting from 1
    // Sum of arithmetic series: (n/2) * (first + last)
    // Here, N is (max_val - min_val + 1)
    // Be careful with large sums, use long long
    
    // Sum of numbers from 1 to max_val
    long long sum_to_max = (long long)max_val * (max_val + 1) / 2;
    // Sum of numbers from 1 to (min_val - 1)
    long long sum_to_min_minus_1 = (long long)(min_val - 1) * (min_val) / 2;
    
    expected_sum = sum_to_max - sum_to_min_minus_1;

    // Step 2: Calculate the actual sum of elements in the input array
    for (int i = 0; i < n; i++) {
        actual_sum += arr[i];
    }

    // Step 3: The difference is the missing element
    return (int)(expected_sum - actual_sum);
}

int main() {
    // Example 1: Single missing element
    int arr1[] = {1, 2, 3, 5, 6, 7, 8, 9, 10};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int min_val1 = 1;
    int max_val1 = 10; // Range 1 to 10, total 10 elements expected. arr1 has 9.
    
    printf("Array: {1, 2, 3, 5, 6, 7, 8, 9, 10}, Range [1, 10]\n");
    int missing_elem1 = findSingleMissingWithSummation(arr1, n1, min_val1, max_val1);
    printf("Single missing element: %d\n\n", missing_elem1);

    // Example 2: Another range
    int arr2[] = {10, 11, 12, 14, 15};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    int min_val2 = 10;
    int max_val2 = 15; // Range 10 to 15, total 6 elements expected. arr2 has 5.
    
    printf("Array: {10, 11, 12, 14, 15}, Range [10, 15]\n");
    int missing_elem2 = findSingleMissingWithSummation(arr2, n2, min_val2, max_val2);
    printf("Single missing element: %d\n\n", missing_elem2);

    // Note: This approach only works if exactly one element is missing.
    // For multiple missing elements, it will yield an incorrect sum.
    
    return 0;
}