2033. Minimum Operations to Make a Uni-Value Grid

題目 / Problem

中文： 給定一個 m x n 的二維整數陣列 grid 與一個整數 x。每次操作可以對 grid 中任意一個元素加上 x 或減去 x。「Uni-value grid」表示所有元素都相等。請回傳將整個 grid 變成 uni-value grid 所需的最少操作次數；若不可能則回傳 -1。

English: You are given an m x n integer grid grid and an integer x. In one operation, you may add x to or subtract x from any element. A uni-value grid is one whose elements are all equal. Return the minimum number of operations to make the grid uni-value, or -1 if impossible.

Constraints / 限制： - 1 <= m, n and 1 <= m * n <= 10^5 - 1 <= x, grid[i][j] <= 10^4

Example / 範例：

Input : grid = [[2,4],[6,8]], x = 2
Output: 4
解釋：把每個元素都變成 4 → 2 加 2 一次；6 減 2 一次；8 減 2 兩次，共 4 次。

名詞解釋 / Glossary

• Modulo / 取餘運算 (%)：a % x 表示 a 除以 x 的餘數。例如 7 % 3 = 1。本題用來判斷兩個數字「能不能透過加減 x 互相到達」——只有當餘數相同時才行。 / a % x is the remainder of a divided by x. Two numbers can be transformed into each other by repeatedly adding/subtracting x only when they share the same remainder.
• Median / 中位數：把一串數字排序後位於正中央的那一個。當代價函數是「絕對差之和」(Σ |a_i - t|) 時，選中位數 t 可以使總和最小。 / The middle value after sorting. It minimises the sum of absolute differences Σ |a_i - t|, which is exactly our cost (each operation moves one element by x).
• Flatten / 攤平：把二維陣列依序放進一維陣列，方便排序。 / Copy a 2-D grid into a 1-D array so we can sort it.
• qsort (C) / std::sort (C++)：標準函式庫的排序函式；C 的 qsort 需要使用者提供比較函式 (compare function)。 / Standard-library sort routines; C's qsort takes a user-supplied comparator.
• Pointer dereference / 指標解參考 (*p)：取得指標 p 指向的值。C 的比較函式收到的是 void*，必須先轉型再 * 取值。 / *p reads the value the pointer p points to; C comparators receive void* arguments that must be cast first.

思路

中文： 暴力作法是「枚舉目標值 t，計算把每個元素變成 t 的步數總和」，但 t 的範圍很大，行不通。我們先想：兩個數 a、b 能透過加減 x 變得相等，當且僅當 (a - b) 是 x 的倍數，也就是 a % x == b % x。所以第一步檢查所有元素的 % x 是否一致；不一致就回傳 -1。一旦餘數相同，每個元素 a 變成目標 t 所需操作數恰好是 |a - t| / x。總成本 Σ |a_i - t| / x 在 t 取中位數時最小（這是經典結論：在數線上選一個點，使到所有點距離之和最小，最佳點就是中位數）。所以策略是：攤平 → 檢查餘數 → 排序 → 取中位數 → 累加 |a_i - median| / x。為了避免反覆除法誤差，可以先全部加總絕對差再除以 x。

English: Brute-forcing every possible target t is hopeless because t is unbounded. Observe that two numbers a and b can be made equal by ±x steps iff (a − b) is a multiple of x, i.e. a % x == b % x. So first verify every element shares the same remainder modulo x; otherwise return -1. Once the remainder check passes, turning element a into target t costs exactly |a − t| / x operations. Minimising Σ |a_i − t| / x over t is the classic "1-D facility location" problem — the optimum is the median of the array. So the algorithm is: flatten the grid → check remainders → sort → pick the median → sum the absolute differences and divide by x. Summing first and dividing once at the end keeps the arithmetic clean.

逐步走查 / Walkthrough

Take grid = [[2,4],[6,8]], x = 2.

(若挑 median = 4：|2−4|+|4−4|+|6−4|+|8−4| = 2+0+2+4 = 8，答案一樣。中位數左右兩個皆最佳。)

Solution — C

/*
 * 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);
}

Solution — C++

/*
 * Same algorithm in idiomatic C++: flatten into std::vector<int>, ensure every value
 * shares grid[0][0] % x, sort, take the median, then sum |a[i] - median| / x.
 * std::vector handles memory; std::nth_element / std::sort do the heavy lifting.
 */

#include <vector>      // std::vector 動態陣列 / dynamic array container
#include <algorithm>   // std::sort, std::abs 等演算法 / algorithms
#include <cstdint>     // int64_t 64-bit integer

class Solution {
public:
    int minOperations(std::vector<std::vector<int>>& grid, int x) {
        // 把所有元素丟進一維 vector / flatten the 2-D grid into one vector
        std::vector<int> a;
        // reserve 預先配置空間，避免 push_back 反覆重新配置 / pre-allocate capacity
        a.reserve(static_cast<size_t>(grid.size()) * grid[0].size());

        int rem = grid[0][0] % x;   // 餘數基準 / baseline remainder

        // range-for: 直接走訪每一列；用 const 參考避免複製 / iterate rows by const ref
        for (const auto& row : grid) {
            for (int v : row) {                 // 走訪每個值 / iterate each value
                if (v % x != rem) return -1;    // 餘數不同就不可能 / impossible
                a.push_back(v);                 // 加入攤平陣列 / append to flat array
            }
        }

        // std::sort 預設升序，需要 #include <algorithm> / sorts a in ascending order
        std::sort(a.begin(), a.end());

        int median = a[a.size() / 2];   // 中位數 / median element

        // 用 long long (即 int64_t) 累加避免溢位 / 64-bit accumulator avoids overflow
        long long sum = 0;
        for (int v : a) {
            sum += std::abs(v - median);   // std::abs 取絕對值 / absolute difference
        }

        // 每步移動 x，故總步數 = 距離和 / x / each step shifts by x
        return static_cast<int>(sum / x);
    }
};

複雜度 / Complexity

• Time: O(N log N)，其中 N = m * n。攤平與餘數檢查是 O(N)；瓶頸在排序的 O(N log N)；最後求和又是一次 O(N)。 / Flattening and the remainder check are O(N); sorting dominates at O(N log N); the final summation is O(N).
• Space: O(N)，用來存放攤平後的一維陣列；排序為原地排序，不增加額外空間。 / We allocate one flat array of size N; the sort itself is in-place.

進階：可以用 nth_element（C++）或 quickselect 把找中位數降到平均 O(N)，整體仍為 O(N)，但對初學者來說 sort 最直觀。 / Using nth_element / quickselect would drop the median step to expected O(N) total, but sort is clearer for beginners.

Pitfalls & Edge Cases

• 餘數判斷別漏 / Don't skip the remainder check. 沒有共同餘數時答案是 -1，必須在排序前檢查每一個元素，否則會回傳一個錯誤的數字。 / Without a common remainder the grid is unreachable; check every cell, not just the first two.
• 整數溢位 / Integer overflow. m * n 可達 10^5，每個元素可達 10^4，距離總和最壞接近 10^9，雖然剛好在 int 範圍內，但用 long long / int64_t 累加更保險。 / The worst-case sum is close to 10^9; use a 64-bit accumulator to be safe.
• 取中位數 / Choosing the median. 偶數長度時 a[n/2] 與 a[n/2 - 1] 兩者皆為最佳；任選其一即可，不必平均。 / For even-length arrays either middle index gives the optimum; no need to average them.
• 不要逐元素除以 x / Don't divide inside the loop. 雖然數學上等價，但先全部相加再除一次更乾淨，也避免 int 截斷誤差。 / Sum first then divide once — clearer and avoids accidental integer truncation per term.
• 比較函式不要寫 return a - b; / Avoid return a - b; in C comparators. 雖然本題值都很小不會溢位，但養成 (a>b) - (a<b) 的習慣可避免將來踩雷。 / Subtraction can overflow on larger inputs; the (a>b) - (a<b) pattern is overflow-safe.
• 記得 free / Remember to free. C 版本 malloc 之後在所有回傳路徑（含 -1 的提前回傳）都要釋放。 / Free the malloc'd buffer on every return path, including the early -1 exit.