Question Link : 1497. Check If Array Pairs Are Divisible by k
[Problem Statement]
Given an array of integers arr
of even length n
and an integer k
, we need to determine if it's possible to divide the array into exactly n/2
pairs such that the sum of each pair is divisible by k
. The function should return true
if such a division is possible, and false
otherwise.
Key Insight
The crucial insight that makes this algorithm efficient is based on the properties of modular arithmetic:
- If
(a + b) % k == 0
, then(a % k + b % k) % k == 0
. - This means that for two numbers to sum to a multiple of
k
, their remainders when divided byk
must sum tok
(or 0, which is the same in modular arithmetic).
Algorithm Steps
-
Initialize Remainder Count:
- Create an array
remainders
of lengthk
, initialized with zeros. - This array will count how many numbers in
arr
have each possible remainder when divided byk
.
- Create an array
-
Count Remainders:
- Iterate through each number
num
in the input arrayarr
. - Calculate its remainder when divided by
k
using((num % k) + k) % k
. - Increment the count for this remainder in the
remainders
array.
- Iterate through each number
-
Check Pairing Possibility:
- Iterate through the remainders from 0 to
k/2
: a. For remainder 0 andk/2
(ifk
is even):- Check if the count is even. If not, return
false
. b. For all other remaindersi
: - Check if the count of remainder
i
equals the count of remainderk-i
. - If not, return
false
.
- Check if the count is even. If not, return
- Iterate through the remainders from 0 to
-
Return Result:
- If all checks pass, return
true
.
- If all checks pass, return
Detailed Breakdown
Counting Remainders
for (let num of arr) {
remainders[((num % k) + k) % k]++;
}
- We use
((num % k) + k) % k
instead of justnum % k
to handle negative numbers correctly. - This ensures all remainders are in the range [0, k-1].
Checking Pairing Possibility
for (let i = 0; i <= k / 2; i++) {
if (i === 0 || (k % 2 === 0 && i === k / 2)) {
if (remainders[i] % 2 !== 0) return false;
} else {
if (remainders[i] !== remainders[k - i]) return false;
}
}
- We only need to check up to
k/2
because remainders pair symmetrically. - For remainder 0 and
k/2
(whenk
is even), we need an even count because these can only pair with themselves. - For all other remainders
i
, we need the count ofi
to equal the count ofk-i
, as these will pair with each other.
Time and Space Complexity
- Time Complexity: O(n + k), where n is the length of
arr
.- We iterate through
arr
once to count remainders: O(n) - We then iterate through half of
k
to check pairing: O(k/2)
- We iterate through
- Space Complexity: O(k) for the
remainders
array.
Why This Works
- By counting remainders, we reduce the problem from checking every possible pair (which would be O(n^2)) to checking if remainders can be paired (which is O(n + k)).
- The pairing check ensures that for every number with remainder
i
, there's a corresponding number with remainderk-i
to pair with it, such that their sum is divisible byk
.
Edge Cases and Considerations
- The algorithm correctly handles negative numbers.
- It works for any positive integer
k
. - It implicitly handles the case where some numbers in
arr
are already divisible byk
(remainder 0).
This algorithm efficiently solves the problem by leveraging properties of modular arithmetic, avoiding the need to actually form the pairs or check every possible pairing.
Top comments (0)