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.
The problem can be approached by first sorting the data of interest and then using the two-pointer technique to solve it efficiently. This method leverages the sorted nature of the data to reduce the complexity of finding comparisons or sums. The two-pointer technique usually involves placing two pointers at different positions in the array and moving them according to the condition checks on the sum or comparison of their pointed values. This allows for efficient traversal with lesser computations.
This C code first sorts the array using quicksort for simplicity and then uses two pointers to find if there are any two numbers in the array which sum up to 0. The sorted array helps in deciding which pointer to move based on the sum of the pointed numbers. This reduces the problem to linear complexity after sorting.
Time Complexity: O(n log n) due to sorting and O(n) due to the two-pointer technique, resulting in O(n log n).
Space Complexity: O(1) since the solution uses no additional space except input array.
An efficient alternative to sorting could be the usage of a hash table (or unordered map) that enables O(1) average-time complexity for search operations. By inserting each element into the hash table and checking if the complementary value (to make a sum zero) exists, one can get the desired pair in linear time without needing to sort the entire array.
This Python solution uses a dictionary to store elements. It then checks for each element if its negation exists in the dictionary. If a complement is found, a solution is printed, otherwise the iteration continues until all elements are processed.
Time Complexity: O(n) on average for insertion and look-up.
Space Complexity: O(n) due to storage in the hash map.
The sum of two numbers a and b is divisible by k if and only if the sum of their remainders when divided by k is divisible by k.
Therefore, we can count the remainder of each number in the array when divided by k, and record them in an array cnt. Then we traverse the array cnt. For each number i in the range [1,..k-1], if the values of cnt[i] and cnt[k-i] are not equal, it means we cannot divide the numbers in the array into n/2 pairs such that the sum of each pair is divisible by k. Similarly, if the value of cnt[0] is not even, it also means we cannot divide the numbers in the array into n/2 pairs such that the sum of each pair is divisible by k.
The time complexity is O(n), where n is the length of the array arr. The space complexity is O(k).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Use Sorting and Two-Pointer Technique | Time Complexity: O(n log n) due to sorting and O(n) due to the two-pointer technique, resulting in O(n log n). |
| Approach 2: Utilize Hashing for Faster Look-up | Time Complexity: O(n) on average for insertion and look-up. |
| Counting Remainders | — |
| 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 |
Leetcode 1497. Check If Array Pairs Are Divisible by k • Fraz • 19,743 views views
Watch 9 more video solutions →Practice Check If Array Pairs Are Divisible by k with our built-in code editor and test cases.
Practice on FleetCode