Count Pairs with equal elements and Divisible Index Sum
Given an array arr[] of length N and an integer k. You have to return the count of all the pairs (i, j) such that:
- arr[i] == arr[j]
- i<j
- (i+j) is divisible by k
Examples:
Input: N = 5, k = 3, arr[] = {1, 2, 3, 2, 1}
Output: 2
Explanation:
- arr[2] = arr[4] and 2<4 , (2+4) = 6 is divisible by 3.
- arr[1] = arr[5] and 1<5 , (1+5) = 6 is divisible by 3.
Input: N = 6, k = 4, arr[] = {1, 1, 1, 1, 1, 1}
Output: 3
Explanation:
- arr[1] = arr[3] and 1<3, (1+3) = 4 is divisible by 4.
- arr[2] = arr[6] and 2<6, (2+6) = 8 is divisible by 4.
- arr[3] = arr[5] and 3<5, (3+5) = 8 is divisible by 4.
Approach: This can be solved with the following idea:
Using Map data structure, Create a a list of indexes. For each value, find number of indexes divisible by k and the count of the indexes in ans.
Below are the steps involved:
- Create a map containing:
- Key as a integer.
- Value as a vector of integers.
- Iterate over array, insert values in map.
- Iterate over map:
- For each value, Iterate over vector containing indexes:
- Count total number of pairs possible whose sum is divisible by k.
- Add the count to ans.
- For each value, Iterate over vector containing indexes:
- Return ans.
Below is the implementation of the code:
C++
// C++ code for the above approach: #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to calculate number of pairs int CountPairs( int N, int k, vector< int >& v) { unordered_map< int , vector< int > > M; // Iterate over the array, store // their indexes for ( int i = 0; i < N; i++) { M[v[i]].push_back((i + 1) % k); } long long ans = 0; for ( auto x : M) { // Iterate over the vector auto & y = x.second; unordered_map< int , int > mod; for ( int i : y) { // Check how may indexes possible int need = (k - i) % k; // Add it to ans ans += mod[need]; mod[i]++; } } // Return total number of pairs return ( int )ans; } // Driver code int main() { int N = 5; int k = 3; vector< int > arr = { 1, 2, 3, 2, 1 }; // Function call cout << CountPairs(N, k, arr); return 0; } |
Java
import java.util.*; public class Main { // Function to calculate number of pairs static int countPairs( int N, int k, int [] v) { Map<Integer, List<Integer>> M = new HashMap<>(); // Iterate over the array, store their indexes for ( int i = 0 ; i < N; i++) { M.computeIfAbsent(v[i], key -> new ArrayList<>()).add((i + 1 ) % k); } long ans = 0 ; for (Map.Entry<Integer, List<Integer>> entry : M.entrySet()) { List<Integer> y = entry.getValue(); Map<Integer, Integer> mod = new HashMap<>(); for ( int i : y) { // Check how many indexes are possible int need = (k - i) % k; // Add it to ans ans += mod.getOrDefault(need, 0 ); mod.put(i, mod.getOrDefault(i, 0 ) + 1 ); } } // Return total number of pairs return ( int ) ans; } // Driver code public static void main(String[] args) { int N = 5 ; int k = 3 ; int [] arr = { 1 , 2 , 3 , 2 , 1 }; // Function call System.out.println(countPairs(N, k, arr)); } } |
Python3
from collections import defaultdict # Function to calculate number of pairs def count_pairs(N, k, v): M = defaultdict( list ) # Iterate over the array, store their indexes for i in range (N): M[v[i]].append((i + 1 ) % k) ans = 0 for x in M.items(): # Iterate over the vector y = x[ 1 ] mod = defaultdict( int ) for i in y: # Check how many indexes possible need = (k - i) % k # Add it to ans ans + = mod[need] mod[i] + = 1 # Return total number of pairs return int (ans) # Driver code N = 5 k = 3 arr = [ 1 , 2 , 3 , 2 , 1 ] # Function call print (count_pairs(N, k, arr)) |
C#
using System; using System.Collections.Generic; class GFG { // Function to calculate the number of the pairs static int CountPairs( int N, int k, List< int > v) { Dictionary< int , List< int >> M = new Dictionary< int , List< int >>(); // Iterate over the array // store their indexes for ( int i = 0; i < N; i++) { int val = v[i]; if (!M.ContainsKey(val)) { M[val] = new List< int >(); } M[val].Add((i + 1) % k); } long ans = 0; foreach ( var pair in M) { var y = pair.Value; Dictionary< int , int > mod = new Dictionary< int , int >(); foreach ( int i in y) { // Check how many indexes are possible int need = (k - i) % k; // Add it to ans if (mod.ContainsKey(need)) { ans += mod[need]; } if (!mod.ContainsKey(i)) { mod[i] = 0; } mod[i]++; } } // Return the total number of the pairs return ( int )ans; } // Driver code static void Main() { int N = 5; int k = 3; List< int > arr = new List< int > { 1, 2, 3, 2, 1 }; // Function call Console.WriteLine(CountPairs(N, k, arr)); } } |
Javascript
// JavaScript code for the above approach // Function to calculate number of pairs function countPairs(N, k, v) { const M = new Map(); // Iterate over the array, store their indexes for (let i = 0; i < N; i++) { const index = (i + 1) % k; if (M.has(v[i])) { M.get(v[i]).push(index); } else { M.set(v[i], [index]); } } let ans = 0; for (const [key, value] of M) { const y = value; const mod = new Map(); for (let i = 0; i < y.length; i++) { // Check how many indexes are possible const need = (k - y[i]) % k; // Add it to ans ans += mod.get(need) || 0; mod.set(y[i], (mod.get(y[i]) || 0) + 1); } } // Return total number of pairs return ans; } // Inputs const N = 5; const k = 3; const arr = [1, 2, 3, 2, 1]; // Function call console.log(countPairs(N, k, arr)); |
Output
2
Time Complexity: O(N*log N)
Auxiliary Space: O(N)