Problem Statement
Given an integer array arr[] and a positive integer k, count the total number of pairs (i, j) such that:
Example
Input
arr = [2, 2, 1, 7, 5, 3]
k = 4
Output
5
Explanation
The valid pairs are:
(2, 2) → 2 + 2 = 4
(1, 7) → 1 + 7 = 8
(7, 5) → 7 + 5 = 12
(1, 3) → 1 + 3 = 4
(5, 3) → 5 + 3 = 8
All these sums are divisible by 4.
Brute Force Approach
The simplest solution is to check every possible pair.
int count = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if ((arr[i] + arr[j]) % k == 0) {
count++;
}
}
}
Complexity
Time Complexity: O(n²)
Space Complexity: O(1)
This approach is slow because every possible pair is checked.
Optimized Approach (Using Remainders)
Instead of checking every pair, we can use modulo arithmetic.
Important Observation
Suppose:
a % k = r1
b % k = r2
Then:
(a + b) % k == 0
only if:
(r1 + r2) % k == 0
This means:
If one number has remainder r, the other number should have remainder:
k - r
or
(k - r) % k
Example
arr = [2, 2, 1, 7, 5, 3]
k = 4
Find the remainder of each number.
| Number | Remainder |
|---|
| 2 | 2 |
| 2 | 2 |
| 1 | 1 |
| 7 | 3 |
| 5 | 1 |
| 3 | 3 |
Now notice:
Because:
1 + 3 = 4
2 + 2 = 4
Both are divisible by 4.
Frequency Array
Create an array:
int[] freq = new int[k];
Each index stores how many numbers with that remainder have already appeared.
For example:
freq[0] -> count of remainder 0
freq[1] -> count of remainder 1
freq[2] -> count of remainder 2
...
freq[k - 1]
Complete Code
class Solution {
public int countKdivPairs(int[] arr, int k) {
int[] freq = new int[k];
int count = 0;
for (int num : arr) {
int rem = num % k;
int need = (k - rem) % k;
count += freq[need];
freq[rem]++;
}
return count;
}
}
Line-by-Line Explanation
Class
class Solution {
GeeksforGeeks expects the solution inside a class named Solution.
Function
public int countKdivPairs(int[] arr, int k)
Parameters
arr → Input array
k → Divisor
Returns
The number of valid pairs.
Frequency Array
int[] freq = new int[k];
Suppose:
k = 4
Then:
freq = [0, 0, 0, 0]
Meaning:
freq[0] = count of remainder 0
freq[1] = count of remainder 1
freq[2] = count of remainder 2
freq[3] = count of remainder 3
Initially, all counts are zero.
Count Variable
int count = 0;
Stores the final answer.
Enhanced For Loop
for (int num : arr)
Visits every element in the array.
For:
arr = [2, 2, 1, 7, 5, 3]
Iteration order:
2
2
1
7
5
3
Find Remainder
int rem = num % k;
Example:
num = 7
k = 4
rem = 7 % 4
rem = 3
Find Required Remainder
int need = (k - rem) % k;
This is the remainder needed to make the sum divisible by k.
Example 1
k = 4
rem = 1
need = (4 - 1) % 4
need = 3
Need remainder 3.
Example 2
rem = 2
need = (4 - 2) % 4
need = 2
Need another remainder 2.
Example 3
rem = 0
need = (4 - 0) % 4
need = 0
Remainder 0 pairs with itself.
Add Previous Matching Numbers
count += freq[need];
Suppose:
need = 3
freq[3] = 5
That means there are already 5 numbers whose remainder is 3.
The current number forms:
5 new pairs
So:
count += 5;
Update Frequency
freq[rem]++;
Store the current remainder for future numbers.
Example:
rem = 2
freq[2]++;
Before:
freq[2] = 3
After:
freq[2] = 4
Return Answer
return count;
Returns the total number of valid pairs.
Dry Run
arr = [2, 2, 1, 7, 5, 3]
k = 4
Initially:
freq = [0, 0, 0, 0]
count = 0
Iteration 1
num = 2
rem = 2
need = 2
count += freq[2]
count += 0
Update:
freq[2]++
freq = [0, 0, 1, 0]
Iteration 2
num = 2
rem = 2
need = 2
count += freq[2]
count = 1
Update:
freq = [0, 0, 2, 0]
Iteration 3
num = 1
rem = 1
need = 3
freq[3] = 0
count = 1
Update:
freq = [0, 1, 2, 0]
Iteration 4
num = 7
rem = 3
need = 1
freq[1] = 1
count = 2
Update:
freq = [0, 1, 2, 1]
Iteration 5
num = 5
rem = 1
need = 3
freq[3] = 1
count = 3
Update:
freq = [0, 2, 2, 1]
Iteration 6
num = 3
rem = 3
need = 1
freq[1] = 2
count = 5
Update:
freq = [0, 2, 2, 2]
Final Answer
5
Why (k - rem) % k Instead of k - rem?
Consider:
k = 4
rem = 0
If we write:
need = k - rem
need = 4
But remainder 4 does not exist.
Valid remainders are:
0
1
2
3
Using:
(k - rem) % k
gives:
(4 - 0) % 4
= 0
which is correct.
Complexity Analysis
Time Complexity
Each element is processed exactly once.
O(n)
Space Complexity
The frequency array stores k elements.
O(k)
Key Takeaways
Instead of checking every pair, compare remainders.
Use a frequency array to count how many numbers with each remainder have been seen.
For each number, calculate its complementary remainder using (k - rem) % k.
Add the count of previously seen complementary remainders to the answer, then record the current remainder.
This reduces the solution from O(n²) to O(n), making it efficient for large input sizes.
Summary
To count pairs whose sum is divisible by k, we can avoid checking all possible pairs by using remainder arithmetic and a frequency array. For each element, we determine the complementary remainder needed to form a sum divisible by k, count all previously seen matching remainders, and then update the frequency array. This approach processes the array in a single pass and improves the time complexity from O(n²) to O(n).
Join the conversation! Your thoughts help the community grow.