Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1497.html
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.
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 == n
1 <= n <= 10^5
n
is even.-10^9 <= arr[i] <= 10^9
1 <= k <= 10^5
Related Topics:
Array, Math, Greedy
Solution 1.
Use a map to store the frequencies of remainders and check if each remainder satisfies the requirement.
- If there are odd number
0
remainders, return false - For
1 <= i < k / 2
, ifm[i] != m[k - i]
, return false.
If k
is an even number, we can return false if m[k / 2] % 2 != 0
but it’s not needed because if m[k / 2]
is odd, one of the above conditions above must be false.
// OJ: https://leetcode.com/problems/check-if-array-pairs-are-divisible-by-k/
// Time: O(N + K)
// Space: O(K)
class Solution {
public:
bool canArrange(vector<int>& A, int k) {
unordered_map<int, int> m;
for (int n : A) m[(n % k + k) % k]++;
if (m[0] % 2) return false;
for (int i = 1; i < k / 2; ++i) {
if (m[i] != m[k - i]) return false;
}
return true;
}
};
Solution 2.
// OJ: https://leetcode.com/problems/check-if-array-pairs-are-divisible-by-k/
// Time: O(N)
// Space: O(K)
class Solution {
public:
bool canArrange(vector<int>& A, int k) {
unordered_map<int, int> m;
for (int &n : A) {
n = (n % k + k) % k;
m[n]++;
}
for (int n : A) {
if ((n == 0 && m[n] % 2) || (n && m[n] != m[k - n])) return false;
}
return true;
}
};
-
class Solution { public boolean canArrange(int[] arr, int k) { int length = arr.length; if (length % 2 != 0) return false; Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int num : arr) { int remainder = num % k; if (remainder < 0) remainder += k; int count = map.getOrDefault(remainder, 0) + 1; map.put(remainder, count); } int count0 = map.getOrDefault(0, 0); if (count0 % 2 != 0) return false; if (k % 2 == 0) { int countHalf = map.getOrDefault(k / 2, 0); if (countHalf % 2 != 0) return false; } int half = k / 2; for (int i = 1; i <= half; i++) { int count1 = map.getOrDefault(i, 0); int count2 = map.getOrDefault(k - i, 0); if (count1 != count2) return false; } return true; } } ############ class Solution { public boolean canArrange(int[] arr, int k) { int[] cnt = new int[k]; for (int x : arr) { ++cnt[(x % k + k) % k]; } for (int i = 1; i < k; ++i) { if (cnt[i] != cnt[k - i]) { return false; } } return cnt[0] % 2 == 0; } }
-
// OJ: https://leetcode.com/problems/check-if-array-pairs-are-divisible-by-k/ // Time: O(N + K) // Space: O(K) class Solution { public: bool canArrange(vector<int>& A, int k) { unordered_map<int, int> m; for (int n : A) m[(n % k + k) % k]++; if (m[0] % 2) return false; for (int i = 1; i < k / 2; ++i) { if (m[i] != m[k - i]) return false; } return true; } };
-
class Solution: def canArrange(self, arr: List[int], k: int) -> bool: mod = [0] * k for v in arr: mod[v % k] += 1 return all(mod[i] == mod[k - i] for i in range(1, k)) and mod[0] % 2 == 0
-
func canArrange(arr []int, k int) bool { cnt := make([]int, k) for _, x := range arr { cnt[(x%k+k)%k]++ } for i := 1; i < k; i++ { if cnt[i] != cnt[k-i] { return false } } return cnt[0]%2 == 0 }