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
}