Skip to main content
Talentd

Check If Array Pairs Are Divisible by k - Solution & Explanation

MediumArrayHash TableCounting14 min readAsked at: Amazon, Microsoft, Meta +5
Practice this problem

Problem Statement

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 == n
  • 1 <= n <= 105
  • n is even.
  • -109 <= arr[i] <= 109
  • 1 <= k <= 105

Approach Overview

Problem 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 1: Approach 1: Use Sorting and Two-Pointer Technique

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.

Code

CC++

C

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Utilize Hashing for Faster Look-up

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.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n) on average for insertion and look-up.
Space Complexity: O(n) due to storage in the hash map.

Try this approach in the editor →

Approach 3: Counting Remainders

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).

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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).
Space Complexity: O(1) since the solution uses no additional space except input array.

Approach 2: Utilize Hashing for Faster Look-up

Time Complexity: O(n) on average for insertion and look-up.
Space Complexity: O(n) due to storage in the hash map.

Counting Remainders—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting + Two PointersO(n log n)O(1)When avoiding extra memory or when the array is already sorted
Hash Map Remainder CountingO(n)O(k)General case and interview-preferred optimal solution

Video Solution

Leetcode 1497. Check If Array Pairs Are Divisible by k • Fraz • 19,770 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Check If Array Pairs Are Divisible by k easy or hard?
The problem is rated Medium on LeetCode. The implementation is straightforward once you recognize the remainder complement rule, but identifying that modular arithmetic insight is what makes it a typical medium-level interview question.
Check If Array Pairs Are Divisible by k Python/Java solution
Python and Java solutions typically use a dictionary or HashMap to track remainder frequencies. After counting remainders, iterate through the map to ensure every remainder r has a matching k - r frequency and handle special cases like remainder 0.
How to solve Check If Array Pairs Are Divisible by k in O(n)?
Compute num % k for every element and store frequencies in a hash map or array. For each remainder r, ensure its frequency matches the frequency of k - r. Handle edge cases where r = 0 (must be even count) and when r = k/2 if k is even. This single pass plus validation gives an O(n) solution.
What is the best approach for Check If Array Pairs Are Divisible by k?
The best approach uses hashing with remainder counting. Compute each element's remainder modulo k and store frequencies in a hash map. For a valid pairing, the count of remainder r must equal the count of k - r, and remainder 0 values must appear an even number of times. This approach runs in O(n) time with O(k) space.
Is Check If Array Pairs Are Divisible by k asked at Google/Amazon/Meta?
Variants of remainder pairing and modular arithmetic problems appear in interviews at companies like Amazon and Google. These companies often test hash map reasoning, complement matching, and array frequency techniques similar to this problem.
What data structure is used in Check If Array Pairs Are Divisible by k?
A hash table (or frequency array) stores counts of each remainder when elements are divided by k. This structure enables constant-time lookup to verify that each remainder has a matching complementary remainder.
What is the time complexity of Check If Array Pairs Are Divisible by k?
The optimal solution runs in O(n) time by scanning the array once and counting remainders in a hash map. Validation of remainder pairs takes O(k). The space complexity is O(k) because at most k remainder values are stored.

Ready to solve this problem?

Practice Check If Array Pairs Are Divisible by k with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Array Pairs Divisible by K

Next

Count Pairs That Form a Complete Day I