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 == n
1 <= n <= 105
n
is even.-109 <= arr[i] <= 109
1 <= 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
}