題目敘述 Check If Array Pairs Are Divisible by k
給定一個長度為偶數的整數陣列arr，和一個整數k 。
我們想把陣列元素兩兩一組組成pair，使得每個pair的總和可以被k整除。
如果做得到，返回True。如果不行，返回False。
測試範例
Example 1:
Input: arr = [1,2,3,4,5,10,6,7,8,9], k = 5
Output: true
Explanation: Pairs are (1,9),(2,8),(3,7),(4,6) and (5,10).
Example 2:
Input: arr = [1,2,3,4,5,6], k = 7
Output: true
Explanation: Pairs are (1,6),(2,5) and(3,4).
Example 3:
Input: arr = [1,2,3,4,5,6], k = 10
Output: false
Explanation: You can try all possible pairs to see that there is no way to divide arr into 3 pairs each with sum divisible by 10.
約束條件
Constraints:
arr.length == n
arr陣列長度= n
1 <= n <= 10^5
n 介於1~十萬之間。
nis even.
陣列長度n是偶數
-10^9 <= arr[i] <= 10^9
每個陣列元素介於 負十億~正十億之間
1 <= k <= 10^5
k值介於1~十萬之間。
演算法 餘數配對
從餘數去做配對
餘1 的和 餘k-1的去配對
餘2 的和 餘k-2的去配對
依此類推...
假如彼此的出現次數不相等，代表無法完美配對，直接返回False。
接著，有兩個Special Case要特別處理。
餘k//2 的和 餘k//2的去配對，所以pair數只有一半而已。
餘0 的和 餘0的去配對，所以pair數也只有一半而已。
如果最後pair總數 = n // 2 = 陣列長度 // 2，
代表我們可以把陣列元素兩兩一組組成pair，使得每個pair的總和可以被k整除。
做得到，返回True。
否則，返回False。
程式碼 餘數配對
class Solution:
def canArrange(self, arr: List[int], k: int) -> bool:
# Length of array
n = len(arr)
# key: remainder of mod k
# value: total counting of number with respect to mod k
count = [0 for _ in range(k) ]
for num in arr:
count[num%k] +=1
# Try to make pair with 1 mod k and k-1 mod k
# 2 mod k and k-2 mod k
# and so on...
i,j =1,k-1
pairs = 0
while i<j :
# Number of i mod k =/= Number of j mod k
# We cannot make exactly n / 2 pairs
if count[i]!=count[j]:
return False
pairs += count[i]
i+=1
j-=1
# Try to make pair with k/2 mod k and k/2 mod k
if i==j:
pairs+=count[i]//2
# Try to make pair with 0 mod k and 0 mod k
pairs+= count[0]//2
return pairs == n//2
複雜度分析
時間複雜度: O(n)
掃描每個數字一次，建立count表格，紀錄mod k 對應的餘數出現次數。
空間複雜度: O(k)
count表格紀錄從餘0~餘k-1的出現次數，表格大小為O(k)
