🔗 🟡 1497. Check If Array Pairs Are Divisible by k 1787

tags: `Weekly Contest 195` `陣列(Array)` `雜湊表(Hash Table)` `計數(Counting)`

題意

給定一個長度為偶數的整數陣列 $arr$ 和一個整數 $k$ ，

請判斷是否可以將陣列中的元素兩兩配對，使得每對元素的和都能被 $k$ 整除。

如果存在這樣的配對方式，返回 $true$ ，否則返回 $false$ 。

約束條件

$n = \text{arr.length}$ 是偶數
$1 \leq n \leq 10^5$
$-10^9 \leq \text{arr[i]} \leq 10^9$
$1 \leq k \leq 10^5$

思路：統計餘數

首先思考哪些數字可以配對，根據題意，如果 $(a + b) \bmod k = 0$ ，則 $a$ 和 $b$ 可以配對。而這個條件可以轉換為 $(a \bmod k + b \bmod k) \bmod k = 0$ ，即 $a \bmod k + b \bmod k = 0$ 或 $a \bmod k + b \bmod k = k$ 。這裡先假設餘數為正數，因此 $a \bmod k$ 和 $b \bmod k$ 的範圍皆為 $0$ 到 $k-1$ 。

因此，我們可以遍歷陣列，計算每個數字除以 $k$ 的餘數，並統計每種餘數出現的次數。由於餘數的範圍為 $0$ 到 $k-1$ ，所以可以使用長度為 $k$ 的陣列 $cnt$ 來記錄每種餘數出現的次數，當然也可以使用雜湊表(Hash Table)來記錄。

接著，我們檢查是否能夠兩兩配對，使得每對元素的和都能被 $k$ 整除。

餘數為 $0$ 的元素可以與自己配對，所以其數量必須為偶數。
對於餘數 $i$ （ $1 \leq i < \frac{k+1}{2}$ ），需要有相同數量的餘數為 $i$ 和 $k-i$ 的元素，即 $cnt[i] = cnt[k-i]$ ，這樣它們的和才能被 $k$ 整除。
當 $k$ 為偶數時，餘數為 $\frac{k}{2}$ 的元素必須成對出現，因為 $\frac{k}{2} + \frac{k}{2} = k$ 也是被 $k$ 整除的。

由於題目確保陣列的長度為偶數，所以條件 1 和條件 3 只需要檢查其中一個即可。

複雜度分析

時間複雜度： $\mathcal{O}(n + k)$ $O (n + k)$ ，其中 $n$ $n$ 是陣列的長度。
- 遍歷陣列計算餘數的數量需要 $\mathcal{O}(n)$ 的時間複雜度。
- 檢查是否能夠兩兩配對需要 $\mathcal{O}(k)$ 的時間複雜度。
空間複雜度： $\mathcal{O}(k)$ $O (k)$ 。
- 需要額外的陣列 $cnt$ 來記錄每種餘數出現的次數。

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        # 統計餘數的數量
        cnt = [0] * k 
        for x in arr:
            cnt[x % k] += 1
        # 檢查是否能夠兩兩配對
        for i in range(1, (k + 1) // 2):
            if cnt[i] != cnt[k - i]:
                return False
        # 處理 K 為偶數的情況，k / 2 的餘數數量必須為偶數
        if k & 1 == 0 and cnt[k // 2] & 1:
            return False
        return True

class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        vector<int> cnt(k, 0);
        for (int x : arr) cnt[(x % k + k) % k]++;
        for (int i = 1; i < (k + 1) / 2; i++) {
            if (cnt[i] != cnt[k - i]) return false;
        }
        if (((k & 1) == 0) && cnt[k / 2] & 1) return false;
        return true;
    }
};