# 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[0] * (count[0] - 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[0]); int k = 6; cout << countpairs(arr,mani , k); return 0; }

**Output: **

OUTPUT: 4

## Leave a Reply

You must be logged in to post a comment.