Example: Minimum Operations to Make Array Elements Equal in C

// Minimum Operations to Make Array Elements Equal
#include <stdio.h>  // Required for printf
#include <stdlib.h> // Required for qsort and abs

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

// Function to calculate the minimum operations
long long minOperations(int arr[], int n) {
    // Step 1: Sort the array
    qsort(arr, n, sizeof(int), compareIntegers);

    // Step 2: Find the median element
    // For an array with N elements, the median is at index N/2
    // If N is even, any element between arr[N/2 - 1] and arr[N/2]
    // will yield the same minimum sum of absolute differences.
    // We can simply pick arr[N/2].
    int median = arr[n / 2];

    // Step 3: Calculate the sum of absolute differences
    long long operations = 0;
    for (int i = 0; i < n; i++) {
        operations += abs(arr[i] - median);
    }

    return operations;
}

int main() {
    // Example 1
    int arr1[] = {1, 2, 3};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    printf("Array: [1, 2, 3]\n");
    printf("Minimum operations: %lld\n\n", minOperations(arr1, n1)); // Expected: 2

    // Example 2
    int arr2[] = {1, 1, 1};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    printf("Array: [1, 1, 1]\n");
    printf("Minimum operations: %lld\n\n", minOperations(arr2, n2)); // Expected: 0

    // Example 3
    int arr3[] = {1, 10, 2, 9};
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
    printf("Array: [1, 10, 2, 9]\n");
    printf("Minimum operations: %lld\n\n", minOperations(arr3, n3)); // Expected: 16 (sorted: [1,2,9,10], median 2 or 9. If 2: |1-2|+|2-2|+|9-2|+|10-2|=1+0+7+8=16. If 9: |1-9|+|2-9|+|9-9|+|10-9|=8+7+0+1=16)

    // Example 4 (Odd number of elements)
    int arr4[] = {5, 1, 2, 4, 3};
    int n4 = sizeof(arr4) / sizeof(arr4[0]);
    printf("Array: [5, 1, 2, 4, 3]\n");
    printf("Minimum operations: %lld\n\n", minOperations(arr4, n4)); // Expected: 6 (sorted: [1,2,3,4,5], median 3. |1-3|+|2-3|+|3-3|+|4-3|+|5-3|=2+1+0+1+2=6)

    return 0;
}