Given an array, arr[] of N elements and an integer K, the task is to find the number of pairs (i, j) such that the absolute value of (arr[i] – arr[j]) is a multiple of K.
Examples:
Input: N = 4, K = 2, arr[] = {1, 2, 3, 4}
Output: 2
Explanation: Total 2 pairs exists in the array with absolute difference divisible by 2. The pairs are: (1, 3), (2, 4).Input: N = 3, K = 3, arr[] = {3, 3, 3}
Output: 3
Explanation: Total 3 pairs exists in this array with absolute difference divisible by 3. The pairs are: (3, 3), (3, 3), (3, 3).
Naive approach: The easiest way is to iterate through every possible pair in the array and if the absolute difference of the numbers is a multiple of K, then increase the count by 1. Print the value of the count after all pairs are processed.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Frequency Array Approach: The approach to solving this problem using a frequency array is discussed in Set-1 of this article. In this approach, we have discussed the approach to solve it using the map.
Efficient Approach: To optimize the above approach, the idea is to observe the fact that for two numbers a[i] and a[j], if a[i] % k = a[j] % k, then abs(a[i] – a[j]) is a multiple of K. Follow the below steps to solve the problem:
- Initialize the variable ans as 0 to store the answer.
- Declare an unordered_map<int, int> count_map[] which stores the count of remainders of array elements with K.
- Iterate over the range [1, N] using the variable index and increment the value arr[index]%k in the count_map by 1 for every index.
- Iterate over all the key-value pairs in the count_map. For each key-value pair:
- The value count_map[rem] is the number of elements whose remainder with K is equal to ‘rem‘.
- For a valid pair to be formed, select any two numbers from the count_map[rem] numbers.
- The number of ways to select two numbers from ‘N‘ numbers is Nc2 = N * (N – 1) / 2.
- Add the answer of all key-value pairs and print ans.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count number of pairs// (i, j) such that abs(arr[i] - arr[j])// is divisible by k.void countOfPairs(int* arr, int N, int K){ // Frequency Map to keep count of // remainders of array elements with K. unordered_map<int, int> count_map; for (int index = 0; index < N; ++index) { count_map[arr[index] % K]++; } // To store the final answer. int ans = 0; for (auto it : count_map) { // Number of ways of selecting any two // numbers from all numbers having the // same remainder is Nc2 = N // * (N - 1) / 2 ans += (it.second * (it.second - 1)) / 2; } // Output the answer. cout << ans << endl;}// Driver Codeint main(){ int K = 2; // Input array int arr[] = { 1, 2, 3, 4 }; // Size of array int N = sizeof arr / sizeof arr[0]; countOfPairs(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to count number of pairs // (i, j) such that Math.abs(arr[i] - arr[j]) // is divisible by k. static void countOfPairs(int[] arr, int N, int K) { // Frequency Map to keep count of // remainders of array elements with K. HashMap<Integer, Integer> count_map = new HashMap<Integer, Integer>(); for (int index = 0; index < N; ++index) { if (count_map.containsKey(arr[index] % K)) { count_map.put(arr[index] % K, count_map.get(arr[index] % K) + 1); } else { count_map.put(arr[index] % K, 1); } } // To store the final answer. int ans = 0; for (Map.Entry<Integer, Integer> it : count_map.entrySet()) { // Number of ways of selecting any two // numbers from all numbers having the // same remainder is Nc2 = N // * (N - 1) / 2 ans += (it.getValue() * (it.getValue() - 1)) / 2; } // Output the answer. System.out.print(ans + "\n"); } // Driver Code public static void main(String[] args) { int K = 2; // Input array int arr[] = { 1, 2, 3, 4 }; // Size of array int N = arr.length; countOfPairs(arr, N, K); }}// This code is contributed by shikhasingrajput |
Python3
# Python Program to implement# the above approach# Function to count number of pairs# (i, j) such that abs(arr[i] - arr[j])# is divisible by k.def countOfPairs(arr, N, K): # Frequency Map to keep count of # remainders of array elements with K. count_map = {} for index in range(N): if (not arr[index] % K in count_map): count_map[arr[index] % K] = 1 else: count_map[arr[index] % K] += 1 # To store the final answer. ans = 0 for val in count_map.values(): # Number of ways of selecting any two # numbers from all numbers having the # same remainder is Nc2 = N # * (N - 1) / 2 ans += (val * (val - 1)) // 2 # Output the answer. print(ans)# Driver CodeK = 2# Input arrayarr = [1, 2, 3, 4]# Size of arrayN = len(arr)countOfPairs(arr, N, K)# This code is contributed by Saurabh Jaiswal |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG { // Function to count number of pairs // (i, j) such that Math.Abs(arr[i] - arr[j]) // is divisible by k. static void countOfPairs(int[] arr, int N, int K) { // Frequency Map to keep count of // remainders of array elements with K. Dictionary<int, int> count_map = new Dictionary<int, int>(); for (int index = 0; index < N; ++index) { if (count_map.ContainsKey(arr[index] % K)) { count_map[arr[index] % K] = count_map[arr[index] % K] + 1; } else { count_map.Add(arr[index] % K, 1); } } // To store the readonly answer. int ans = 0; foreach (KeyValuePair<int, int> it in count_map) { // Number of ways of selecting any two // numbers from all numbers having the // same remainder is Nc2 = N // * (N - 1) / 2 ans += (it.Value * (it.Value - 1)) / 2; } // Output the answer. Console.Write(ans + "\n"); } // Driver Code public static void Main(String[] args) { int K = 2; // Input array int []arr = { 1, 2, 3, 4 }; // Size of array int N = arr.Length; countOfPairs(arr, N, K); }}// This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to count number of pairs // (i, j) such that abs(arr[i] - arr[j]) // is divisible by k. function countOfPairs(arr, N, K) { // Frequency Map to keep count of // remainders of array elements with K. let count_map = new Map(); for (let index = 0; index < N; ++index) { if (!count_map.has(arr[index] % K)) count_map.set(arr[index] % K, 1); else count_map.set(arr[index] % K, count_map.get(arr[index] % K) + 1) } // To store the final answer. let ans = 0; for (let [key, value] of count_map) { // Number of ways of selecting any two // numbers from all numbers having the // same remainder is Nc2 = N // * (N - 1) / 2 ans += (value * (value - 1)) / 2; } // Output the answer. document.write(ans + '<br>'); } // Driver Code let K = 2; // Input array let arr = [1, 2, 3, 4]; // Size of array let N = arr.length; countOfPairs(arr, N, K); // This code is contributed by Potta Lokesh </script> |
Output
2
Time Complexity: O(NlogN)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
