Check If Array Pairs Are Divisible by k — Problem & Solution
Check If Array Pairs Are Divisible by k solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Check If Array Pairs Are Divisible by k is a medium coding problem on arrays, hash table and counting, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Counting
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array arr of even length n and an integer k.
You want to split arr into exactly n / 2 pairs, every element in exactly one pair, such that the sum of each pair is divisible by k.
Return true if such a split exists, and false otherwise.
Example 1
Input: arr = [-1,1,-2,2,3,7], k = 5
Output: true
Explanation: Pairs `(-1,1)`, `(-2,2)` and `(3,7)` sum to 0, 0 and 10, all divisible by 5.
Example 2
Input: arr = [4,4,4,6], k = 10
Output: false
Explanation: A 4 needs a partner leaving remainder 6, and there is only one 6 for three 4s.
Example 3
Input: arr = [5,5,5,5], k = 10
Output: true
Explanation: 5 is exactly half of 10, so 5s pair with each other: `(5,5)` twice.
Constraints
arr.length == n1 <= n <= 10^5n is even-10^9 <= arr[i] <= 10^91 <= k <= 10^5
Hints for Check If Array Pairs Are Divisible by k
Hint 1
Whether
a + bis divisible bykdepends only ona mod kandb mod k.Hint 2
An element with remainder
rneeds a partner with remainderk - r; remainder 0 needs another remainder 0.Hint 3
Count elements per remainder (taking care with negative numbers) and compare
count[r]withcount[k - r].
How to solve Check If Array Pairs Are Divisible by k
Reduce every element to its non-negative remainder modulo k. Remainders r and k - r must be matched one to one, and the self-paired classes (0, and k / 2 when k is even) must each have an even size.
Approach
- Compute
r = ((x % k) + k) % kfor every element and count each remainder. - If
count[0]is odd, return false. - For every other remainder
r: if2r == k, requirecount[r]to be even; otherwise requirecount[r] == count[k - r]. - Return true if every check passes.
Why it works
Two elements can pair only if their remainders add to 0 or k, so each class r can only pair with class k - r. When those classes are distinct, a perfect pairing exists exactly when their sizes match; when a class pairs with itself (r = 0 or r = k / 2), it needs an even size. These classes partition the array, so the conditions together are necessary and sufficient.
Complexity
- Time —
O(n) - Space —
O(min(n, k))
Pitfalls
- In most languages
%of a negative number is negative:-1 % 5is-1, so normalise with((x % k) + k) % k. - Remainder
k / 2for evenkpairs with itself — comparingcount[r]withcount[k - r]there is trivially true and misses an odd count. - With
k = 1every sum is divisible, and every remainder is 0.
Reference solution
Python
from typing import List
from collections import Counter
def canArrange(arr: List[int], k: int) -> bool:
cnt = Counter(x % k for x in arr)
for r, c in cnt.items():
if r == 0 or 2 * r == k:
if c % 2:
return False
elif cnt.get(k - r, 0) != c:
return False
return TrueJava
public static boolean canArrange(int[] arr, int k) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : arr) cnt.merge(((x % k) + k) % k, 1, Integer::sum);
for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {
int r = e.getKey(), c = e.getValue();
if (r == 0 || 2 * r == k) { if (c % 2 != 0) return false; }
else if (cnt.getOrDefault(k - r, 0) != c) return false;
}
return true;
}C++
bool canArrange(vector<int>& arr, int k) {
unordered_map<int, int> cnt;
for (int x : arr) cnt[((x % k) + k) % k]++;
for (auto& e : cnt) {
int r = e.first, c = e.second;
if (r == 0 || 2 * r == k) { if (c % 2 != 0) return false; }
else {
auto it = cnt.find(k - r);
if (it == cnt.end() || it->second != c) return false;
}
}
return true;
}JavaScript
var canArrange = function(arr, k) {
var cnt = new Map();
for (var i = 0; i < arr.length; i++) {
var r = ((arr[i] % k) + k) % k;
cnt.set(r, (cnt.get(r) || 0) + 1);
}
var ok = true;
cnt.forEach(function(c, r) {
if (r === 0 || 2 * r === k) { if (c % 2 !== 0) ok = false; }
else if ((cnt.get(k - r) || 0) !== c) ok = false;
});
return ok;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets