# Count pairs in array whose sum is divisible by K in C++

In this tutorial, we will learn how to count pairs in an array whose sum is divisible by K in C++. Also, given an array and a number K, and we have to count pairs.
For example:

• Given arr[ ] = { 2, 4, 5, 2, 1, 6} and K = 6
• 2+4=6 and that is divisible by 6.
• 4+2 = 6 and that is divisible by 6.
• 5+1 = 6 and that is also divisible by 6.
• 6 is divisilbe by itself.
• Total number of pairs = 4

Simple Approach:

• We will iterate through every pair of the array by using two for loops.
• Count the pairs whose sum is divisible by number.
• Time complexity: O(n^2)

For better performance, we have to reduce this time complexity. So, we will go for a better approach.

Efficient Approach:

• We will use the hashing technique.
• Separate elements of an array into a bucket that separation will depend upon mathematical computation.
• Mathematical computation is their (value mod K).
• The time complexity of this hashing technique: O(n)
• Hence, we have reduced the time complexity of our code.

You may also like:
Find count of multiples of 3 or 5 in a given range in C++

## Count pairs in an array whose sum is divisible by K in C++

Hence, this is implemented code:

```// C++ Program to count pairs
#include<iostream>
#include <bits/stdc++.h>
using namespace std;

// Program to count pairs
int countpairs(int arr[], int mani, int k)
{
// Create a count array to count pairs
int count[k] = { 0 };

// Count occurrences of all remaind.
for (int i = 0; i < mani; i++)
++count[arr[i] % k];

int sumof = count * (count - 1) / 2;

// count for all pairs
for (int i = 1; i <= k / 2 && i != (k- i); i++)
sumof += count[i] * count[k - i];

if (k % 2 == 0)
sumof+= (count[k / 2] * (count[k / 2] - 1) / 2);
return sumof;
}

int main()
{

int arr[] = { 2, 4, 1, 2, 5, 1 };
int mani = sizeof(A) / sizeof(A);
int k = 6;
cout << countpairs(arr,mani , k);

return 0;
}
```

Output:

`OUTPUT:  4`