/*
 * Algorithm: flatten grid into a 1-D array; verify every element shares the same
 * remainder mod x (else impossible). Sort, pick the median, and sum |a[i] - median|;
 * the answer is that sum divided by x, because each ±x step closes a gap of x.
 */

#include <stdlib.h>   // qsort / malloc / free 標準函式庫
#include <stdint.h>   // int64_t 定義 / 64-bit integer type

// 比較函式：qsort 需要這個來決定升序排列 / comparator for ascending qsort
static int cmpAsc(const void *pa, const void *pb) {
    // 先把 void* 轉成 int*，再用 * 解參考取值 / cast void* to int* then dereference
    int a = *(const int *)pa;
    int b = *(const int *)pb;
    // 回傳 a-b：負代表 a 在前，正代表 b 在前 / negative means a comes first
    return (a > b) - (a < b);  // 用減法可能溢位，這寫法安全 / safer than a-b vs overflow
}

int minOperations(int **grid, int gridSize, int *gridColSize, int x) {
    int m = gridSize;             // 行數 / number of rows
    int n = gridColSize[0];       // 列數（每行長度相同）/ columns (all rows same width)
    int total = m * n;            // 元素總數 / total cell count

    // 配置一維陣列存放攤平後的元素 / allocate flat buffer to hold all elements
    int *a = (int *)malloc(sizeof(int) * total);

    int idx = 0;                  // a[] 的寫入索引 / write index for a[]
    int rem = grid[0][0] % x;     // 取第一格的餘數作為基準 / baseline remainder

    // 把 grid 攤平成 a[]，同時檢查餘數一致 / flatten grid and check remainders
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 若任一元素餘數不同就不可能達成 / mismatched remainder => impossible
            if (grid[i][j] % x != rem) {
                free(a);          // 別忘了釋放記憶體 / always free what we malloc'd
                return -1;
            }
            a[idx++] = grid[i][j];   // 寫入並前進索引 / store value, advance index
        }
    }

    // 排序以便取中位數 / sort so we can grab the median
    qsort(a, total, sizeof(int), cmpAsc);

    int median = a[total / 2];    // 中位數位置；偶數長度時取右中即可 / median index

    // 用 int64_t 累加，避免 |a_i - median| 之和超出 int 範圍
    // use 64-bit accumulator to be safe (10^5 * 10^4 = 10^9, near INT_MAX)
    int64_t sum = 0;
    for (int i = 0; i < total; i++) {
        int diff = a[i] - median;        // 差值 / difference
        if (diff < 0) diff = -diff;      // 取絕對值 / absolute value
        sum += diff;                     // 累加 / accumulate
    }

    free(a);                      // 釋放陣列 / release memory before returning
    // 每次操作改變 x，故總步數 = 距離總和 / x / each op moves by x, so divide by x
    return (int)(sum / x);
}