Count Equal and Divisible Pairs in an Array
Problem
Given an array nums and an integer k, return the number of index pairs (i, j) with i < j such that nums[i] = nums[j] and (i · j) is divisible by k.
nums = [3,1,2,2,2,1,3], k = 24def count_pairs(nums, k):
seen = {}
count = 0
for j, v in enumerate(nums):
for i in seen.get(v, []):
if (i * j) % k == 0:
count += 1
seen.setdefault(v, []).append(j)
return countfunction countPairs(nums, k) {
const seen = new Map();
let count = 0;
for (let j = 0; j < nums.length; j++) {
const list = seen.get(nums[j]) || [];
for (const i of list) if ((i * j) % k === 0) count++;
list.push(j);
seen.set(nums[j], list);
}
return count;
}class Solution {
public int countPairs(int[] nums, int k) {
Map<Integer, List<Integer>> seen = new HashMap<>();
int count = 0;
for (int j = 0; j < nums.length; j++) {
List<Integer> list = seen.computeIfAbsent(nums[j], x -> new ArrayList<>());
for (int i : list) if ((i * j) % k == 0) count++;
list.add(j);
}
return count;
}
}int countPairs(vector<int>& nums, int k) {
unordered_map<int, vector<int>> seen;
int count = 0;
for (int j = 0; j < (int)nums.size(); j++) {
for (int i : seen[nums[j]]) if ((i * j) % k == 0) count++;
seen[nums[j]].push_back(j);
}
return count;
}Explanation
A pair counts only when the two elements are equal and their index product is divisible by k. The equality requirement lets us group work by value instead of comparing every pair blindly.
We keep a hash map seen from a value to the list of earlier indices where that value appeared. As we walk index j, every index i already stored under nums[j] is a previous equal element, so (i, j) is an equal pair with i < j.
For each such i we test the divisibility condition (i · j) % k == 0 and increment the counter when it holds. Then we append j to its value's list so future indices can pair with it.
This visits each equal pair exactly once. In the worst case (all values equal) it is O(n²), but it avoids ever comparing unequal elements, and uses O(n) space for the buckets.
Example: [3,1,2,2,2,1,3], k = 2. The 2's sit at indices 2,3,4 giving pairs with products 6, 8, 12 (all even); the 1's at 1,5 give 5 (odd, skip); the 3's at 0,6 give 0 (even). Counting the valid ones yields 4.