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.
Example 4:
Input: arr = [-10,10], k = 2 Output: true
Example 5:
Input: arr = [-1,1,-2,2,-3,3,-4,4], k = 3 Output: true
Constraints:
arr.length == n1 <= n <= 10^5nis even.-10^9 <= arr[i] <= 10^91 <= k <= 10^5
Solution: Mod and Count
Count the frequency of (x % k + k) % k.
f[0] should be even (zero is also even)
f[1] = f[k -1] ((1 + k – 1) % k == 0)
f[2] = f[k -2] ((2 + k – 2) % k == 0)
…
Time complexity: O(n)
Space complexity: O(k)
C++
|
1 2 3 4 5 6 7 8 9 10 11 |
// Author: Huahua class Solution { public: bool canArrange(vector<int>& arr, int k) { vector<int> f(k); for (int x : arr) ++f[(x % k + k) % k]; for (int i = 1; i < k; ++i) if (f[i] != f[k - i]) return false; return f[0] % 2 == 0; } }; |
