Example: Minimum Sum of Absolute Differences using Median in C

// Minimum Sum of Absolute Differences using Median
#include <stdio.h>  // For printf
#include <stdlib.h> // For qsort and abs

// Comparison function for qsort to sort integers in ascending order
int compareIntegers(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    // Example with an odd number of elements
    int arr_odd[] = {1, 2, 9, 2, 7};
    int n_odd = sizeof(arr_odd) / sizeof(arr_odd[0]);

    printf("Original array (odd size): ");
    for (int i = 0; i < n_odd; i++) {
        printf("%d ", arr_odd[i]);
    }
    printf("\n");

    // Step 1: Sort the array
    qsort(arr_odd, n_odd, sizeof(int), compareIntegers);

    // Step 2: Find the median (for odd-sized array, it's the middle element)
    int median_odd = arr_odd[n_odd / 2];

    // Step 3: Calculate the sum of absolute differences with the median
    long long min_sum_odd = 0; // Use long long to prevent overflow for large sums
    for (int i = 0; i < n_odd; i++) {
        min_sum_odd += abs(arr_odd[i] - median_odd);
    }

    printf("Sorted array (odd size): ");
    for (int i = 0; i < n_odd; i++) {
        printf("%d ", arr_odd[i]);
    }
    printf("\n");
    printf("Median for odd size array: %d\n", median_odd);
    printf("Minimum sum of absolute differences for odd size array: %lld\n\n", min_sum_odd);


    // Example with an even number of elements
    int arr_even[] = {1, 2, 10, 2, 7, 8};
    int n_even = sizeof(arr_even) / sizeof(arr_even[0]);

    printf("Original array (even size): ");
    for (int i = 0; i < n_even; i++) {
        printf("%d ", arr_even[i]);
    }
    printf("\n");

    // Step 1: Sort the array
    qsort(arr_even, n_even, sizeof(int), compareIntegers);

    // Step 2: Find one of the medians (for even-sized array, arr[n/2 - 1] or arr[n/2] works)
    // We choose arr[n/2 - 1] here, but arr[n/2] would yield the same minimum sum.
    int median_even = arr_even[n_even / 2 - 1];

    // Step 3: Calculate the sum of absolute differences with the chosen median
    long long min_sum_even = 0;
    for (int i = 0; i < n_even; i++) {
        min_sum_even += abs(arr_even[i] - median_even);
    }

    printf("Sorted array (even size): ");
    for (int i = 0; i < n_even; i++) {
        printf("%d ", arr_even[i]);
    }
    printf("\n");
    printf("Median (chosen) for even size array: %d\n", median_even);
    printf("Minimum sum of absolute differences for even size array: %lld\n", min_sum_even);

    return 0;
}