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