Watch 10 video solutions for Check If Array Pairs Are Divisible by k, a medium level problem involving Array, Hash Table, Counting. This walkthrough by Fraz has 19,743 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 == n1 <= n <= 105n is even.-109 <= arr[i] <= 1091 <= k <= 105Problem Overview: You receive an integer array and a value k. The task is to determine whether the array can be partitioned into pairs such that the sum of every pair is divisible by k. Each element must be used exactly once, so the challenge is verifying that every value finds a compatible partner.
Approach 1: Sorting and Two-Pointer Technique (O(n log n) time, O(1) extra space)
This approach starts by sorting the array so values with similar remainders cluster together. After sorting, compute each element’s remainder with k and use two pointers from opposite ends to attempt forming valid pairs. For any pair (a, b), check if (a + b) % k == 0. Sorting enables structured traversal while two pointers progressively match candidates from both ends of the array.
This method works best when the array is already sorted or when you want a deterministic pairing process without additional memory. The downside is the O(n log n) sorting cost. It also requires careful pointer adjustments when sums fail the divisibility condition. The technique mainly relies on array traversal patterns and controlled pointer movement.
Approach 2: Utilize Hashing for Faster Look-up (O(n) time, O(k) space)
The key observation: if two numbers form a valid pair, their remainders must complement each other. For a number with remainder r, its partner must have remainder (k - r) % k. Iterate through the array and compute num % k. Maintain a frequency map that counts how many times each remainder appears.
After counting, validate the pairing rules. Remainder 0 values must occur an even number of times because they can only pair with each other. For any other remainder r, the count of r must equal the count of k - r. This guarantees every element finds a valid complement whose sum is divisible by k.
This method relies on a hash table to track remainder frequencies and simple arithmetic to verify complements. Because each element is processed once, the total time complexity stays O(n) with O(k) extra space for remainder counts. It’s a classic use of modular arithmetic and counting techniques.
Recommended for interviews: The hashing approach is the expected solution. Interviewers want to see the remainder complement insight and the ability to translate it into a frequency map check. The sorting approach demonstrates problem exploration, but the O(n) hash-based method shows stronger algorithmic reasoning and is typically preferred in coding interviews.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Two Pointers | O(n log n) | O(1) | When avoiding extra memory or when the array is already sorted |
| Hash Map Remainder Counting | O(n) | O(k) | General case and interview-preferred optimal solution |