|
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.
- Return ans.
Below is the implementation of the code:
C++
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int CountPairs(int N, int k, vector<int>& v)
{
unordered_map<int, vector<int> > M;
for (int i = 0; i < N; i++) {
M[v[i]].push_back((i + 1) % k);
}
long long ans = 0;
for (auto x : M) {
auto& y = x.second;
unordered_map<int, int> mod;
for (int i : y) {
int need = (k - i) % k;
ans += mod[need];
mod[i]++;
}
}
return (int)ans;
}
int main()
{
int N = 5;
int k = 3;
vector<int> arr = { 1, 2, 3, 2, 1 };
cout << CountPairs(N, k, arr);
return 0;
}
|
Java
import java.util.*;
public class Main {
static int countPairs(int N, int k, int[] v) {
Map<Integer, List<Integer>> M = new HashMap<>();
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) {
int need = (k - i) % k;
ans += mod.getOrDefault(need, 0);
mod.put(i, mod.getOrDefault(i, 0) + 1);
}
}
return (int) ans;
}
public static void main(String[] args) {
int N = 5;
int k = 3;
int[] arr = {1, 2, 3, 2, 1};
System.out.println(countPairs(N, k, arr));
}
}
|
Python3
from collections import defaultdict
def count_pairs(N, k, v):
M = defaultdict(list)
for i in range(N):
M[v[i]].append((i + 1) % k)
ans = 0
for x in M.items():
y = x[1]
mod = defaultdict(int)
for i in y:
need = (k - i) % k
ans += mod[need]
mod[i] += 1
return int(ans)
N = 5
k = 3
arr = [1, 2, 3, 2, 1]
print(count_pairs(N, k, arr))
|
C#
using System;
using System.Collections.Generic;
class GFG
{
static int CountPairs(int N, int k, List<int> v)
{
Dictionary<int, List<int>> M = new Dictionary<int, List<int>>();
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)
{
int need = (k - i) % k;
if (mod.ContainsKey(need))
{
ans += mod[need];
}
if (!mod.ContainsKey(i))
{
mod[i] = 0;
}
mod[i]++;
}
}
return (int)ans;
}
static void Main()
{
int N = 5;
int k = 3;
List<int> arr = new List<int> { 1, 2, 3, 2, 1 };
Console.WriteLine(CountPairs(N, k, arr));
}
}
|
Javascript
function countPairs(N, k, v) {
const M = new Map();
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++) {
const need = (k - y[i]) % k;
ans += mod.get(need) || 0;
mod.set(y[i], (mod.get(y[i]) || 0) + 1);
}
}
return ans;
}
const N = 5;
const k = 3;
const arr = [1, 2, 3, 2, 1];
console.log(countPairs(N, k, arr));
|
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
|
