1497. Check If Array Pairs Are Divisible by k
Medium
Given an array of integers
arr of even length n and an integer k.We want to divide the array into exactly
n / 2 pairs such that the sum of each pair is divisible by k.Return
true If you can find a way to do that or false otherwise.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 == n1 <= n <= 105nis even.-109 <= arr[i] <= 1091 <= k <= 105
這題只要懂數學原理就會很簡單。
1 % 5 = 1
2 % 5 = 2
3 % 5 = 3
4 % 5 = 4
5 % 5 = 0
6 % 5 = 1
7 % 5 = 2
8 % 5 = 3
9 % 5 = 4
10 % 5 = 0
如果把餘數為 1 的 1 和 餘數為 4 的 9 相加，得到的 10 餘數為 0 。
因此我們可以建個陣列來記錄餘數的數量，再檢查相加等於 k 的兩個餘數數量是否相等。此外，因為題目說陣列長度為偶數，等於 0 的餘數數量也必須是偶數。
Runtime: 109 ms, faster than 90.16%
Memory Usage: 9 MB, less than 91.80%
func canArrange(arr []int, k int) bool {
count := make([]int, k)
for _, val := range arr {
n := val % k
if n<0 { n +=k }
count[n]++
}
for _, val := range arr {
rem1 := val % k
if rem1<0 { rem1+=k }
if rem1==0 {
if count[0]%2 !=0 { return false }
} else {
rem2 := k-rem1
if count[rem1] != count[rem2] { return false }
}
}
return true
}