Absolute difference divisible by K

Absolute difference divisible by K





Given an array of integers of size n and an integer k, find all the pairs in the array whose absolute difference is divisible by k.

Example 1:

Input:
n = 3
arr[] = {3, 7, 11}
k = 4
Output:
3
Explanation:
(11-3) = 8 is divisible by 4
(11-7) = 4 is divisible by 4
(7-3) = 4 is divisible by 4


Example 2:

Input:
n = 4
arr[] = {1, 2, 3, 4}
k = 2
Output :
2
Explanation:
Valid pairs are (1,3), and (2,4).


Solution:


 long long countPairs(int n, int arr[], int k) {

        int a[n];

        map<int, int> m;

        for(int i=0; i<n; i++){

            a[i] = (arr[i]+k)%k;

            m[a[i]]++;

        }

     

        long long int  ans =0;

        for(auto i=m.begin(); i!=m.end(); i++){

            int no = i->second;

            ans = ans + (no*(no-1)/2);

        }

       

        return ans;

    }





fhdfn

Post a Comment

If you have furthur QUERIES please let us know

Previous Post Next Post