Count Equal and Divisible Pairs in an Array solution and explanation
Google
9 more videos on this problem
Count Equal and Divisible Pairs in an Array | Brute Force | Optimal | Detailed Maths | Leetcode 2176codestorywithMIK · 30:04 · 6K views
LeetCode 2176 Count Equal and Divisible Pairs in an Array | Beginner Friendly | Optimal 🔥Code Harmony · 15:32 · 1K views
2176. Count Equal and Divisible Pairs in an Array || Biweekly Contest 72 || Leetcode 2176Bro Coders · 4:31 · 1K views
Count Equal and Divisible Pairs in an Array | 2176 LeetCode | BiWeekly Contest 72 | Brute ForceCodeWithSunny · 3:41 · 700 views
2176. Count Equal and Divisible Pairs in an Array (Leetcode Easy)Programming Live with Larry · 2:35 · 372 views
2176. Count Equal and Divisible Pairs in an Array | Leetcode Daily - PythonLeetcode Daily · 7:55 · 204 views
Count Equal and Divisible Pairs in an Array - LeetCode 2176 - Java Solutionalgobest - Computer Science · 3:34 · 146 views
Leetcode#2176 Count Equal and Divisible Pairs in an Array | C++ WalkthroughJoshProgramin · 6:23 · 110 views
LeetCode 2176 - Count Equal and Divisible Pairs in an Array - JavaAlpha-Code · 2:36 · 103 views
Count Equal and Divisible Pairs in an Array - Leetcode 2176 - PythonTim Huang · 3:25 · 84 views
The problem
nums of length n and an integer k, return the number of pairs (i, j) where 0 <= i < j < n, such that nums[i] == nums[j] and (i * j) is divisible by k.
Example 1:
Input: nums = [3,1,2,2,2,1,3], k = 2 Output: 4 Explanation: There are 4 pairs that meet all the requirements: - nums[0] == nums[6], and 0 * 6 == 0, which is divisible by 2. - nums[2] == nums[3], and 2 * 3 == 6, which is divisible by 2. - nums[2] == nums[4], and 2 * 4 == 8, which is divisible by 2. - nums[3] == nums[4], and 3 * 4 == 12, which is divisible by 2.
Example 2:
Input: nums = [1,2,3,4], k = 1 Output: 0 Explanation: Since no value in nums is repeated, there are no pairs (i,j) that meet all the requirements.
Constraints:
1 <= nums.length <= 1001 <= nums[i], k <= 100
Approach overview
Problem Overview: Given an integer array nums and an integer k, count pairs of indices (i, j) such that i < j, nums[i] == nums[j], and (i * j) % k == 0. The task combines value equality with an index divisibility condition, so you must track both the numbers and their positions.
Approach 1: Brute Force Pair Check (O(n²) time, O(1) space)
Iterate through every pair of indices using two nested loops. For each pair (i, j) where i < j, first check if the values are equal. If nums[i] == nums[j], compute (i * j) % k. When the result is zero, increment the pair count. This approach directly simulates the problem statement and works well for small arrays. Time complexity is O(n²) because every pair is examined, while space complexity remains O(1). Since the problem involves iterating through an array, this method is often the starting point during interviews to demonstrate baseline reasoning.
Approach 2: HashMap Frequency Grouping (O(n²) worst-case time, O(n) space)
Instead of comparing every pair in the array, group indices by their value using a HashMap<value, list of indices>. Iterate through the array once and store each index under its corresponding number. For each group of equal values, only evaluate pairs within that group because unequal numbers can never form valid pairs. Then check the divisibility condition (i * j) % k == 0 for index pairs inside the group. This reduces unnecessary comparisons when the array contains many distinct numbers. The time complexity remains O(n²) in the worst case (when all numbers are identical), but it is significantly faster in typical scenarios with mixed values. Space complexity is O(n) for the map. This method uses a hash table to organize data before processing, a common optimization pattern in array problems.
Recommended for interviews: Start with the brute force approach to show you understand the constraints and conditions clearly. Then move to the HashMap grouping technique to reduce unnecessary comparisons. Interviewers expect you to recognize that equality filtering can be done first using hashing, which demonstrates practical optimization skills even when the theoretical worst-case complexity remains O(n²).
Approach 1: Brute Force Approach
This approach involves iterating over all possible pairs (i, j) using nested loops and checking if the conditions are met.
def count_pairs(nums, k):
count = 0
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] == nums[j] and (i * j) % k == 0:
count += 1
return count
nums = [3, 1, 2, 2, 2, 1, 3]
k = 2
print(count_pairs(nums, k))public class Solution {
public int countPairs(int[] nums, int k) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] == nums[j] && (i * j) % k == 0) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {3, 1, 2, 2, 2, 1, 3};
int k = 2;
System.out.println(sol.countPairs(nums, k));
}
}#include <iostream>
#include <vector>
using namespace std;
int countPairs(vector<int>& nums, int k) {
int count = 0;
int n = nums.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] == nums[j] && (i * j) % k == 0) {
count++;
}
}
}
return count;
}
int main() {
vector<int> nums = {3, 1, 2, 2, 2, 1, 3};
int k = 2;
cout << countPairs(nums, k) << endl;
return 0;
}function countPairs(nums, k) {
let count = 0;
let n = nums.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (nums[i] === nums[j] && (i * j) % k === 0) {
count++;
}
}
}
return count;
}
const nums = [3, 1, 2, 2, 2, 1, 3];
const k = 2;
console.log(countPairs(nums, k));#include <stdio.h>
int countPairs(int* nums, int n, int k) {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] == nums[j] && (i * j) % k == 0) {
count++;
}
}
}
return count;
}
int main() {
int nums[] = {3, 1, 2, 2, 2, 1, 3};
int k = 2;
int length = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", countPairs(nums, length, k));
return 0;
}using System;
public class Solution {
public int CountPairs(int[] nums, int k) {
int count = 0;
int n = nums.Length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] == nums[j] && (i * j) % k == 0) {
count++;
}
}
}
return count;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {3, 1, 2, 2, 2, 1, 3};
int k = 2;
Console.WriteLine(sol.CountPairs(nums, k));
}
}The Python code iterates over all possible index pairs using nested loops and checks both conditions with simple if statements to ensure the conditions are satisfied.
Time Complexity: O(n^2).
Space Complexity: O(1) as only simple variables are used.
Approach 2: HashMap Frequency Counting Approach
Use a hashmap to count occurrences of elements. Check each pair using a single loop by jumping indices where same elements exist. This reduces the number of checks as repeated pairs can be calculated mathematically.
from collections import defaultdict
def count_pairs(nums, k):
index_map = defaultdict(list)
count = 0
for i, num in enumerate(nums):
if num in index_map:
for j in index_map[num]:
if (i * j) % k == 0:
count += 1
index_map[num].append(i)
return count
nums = [3, 1, 2, 2, 2, 1, 3]
k = 2
print(count_pairs(nums, k))import java.util.*;
public class Solution {
public int countPairs(int[] nums, int k) {
Map<Integer, List<Integer>> map = new HashMap<>();
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (!map.containsKey(nums[i])) {
map.put(nums[i], new ArrayList<>());
}
for (int index : map.get(nums[i])) {
if ((index * i) % k == 0) {
count++;
}
}
map.get(nums[i]).add(i);
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {3, 1, 2, 2, 2, 1, 3};
int k = 2;
System.out.println(sol.countPairs(nums, k));
}
}#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int countPairs(vector<int>& nums, int k) {
unordered_map<int, vector<int>> indexMap;
int count = 0;
for (int i = 0; i < nums.size(); i++) {
if (indexMap.find(nums[i]) != indexMap.end()) {
for (int index : indexMap[nums[i]]) {
if ((index * i) % k == 0) {
count++;
}
}
}
indexMap[nums[i]].push_back(i);
}
return count;
}
int main() {
vector<int> nums = {3, 1, 2, 2, 2, 1, 3};
int k = 2;
cout << countPairs(nums, k) << endl;
return 0;
}function countPairs(nums, k) {
const indexMap = new Map();
let count = 0;
for (let i = 0; i < nums.length; i++) {
if (indexMap.has(nums[i])) {
for (let j of indexMap.get(nums[i])) {
if ((i * j) % k === 0) {
count++;
}
}
} else {
indexMap.set(nums[i], []);
}
indexMap.get(nums[i]).push(i);
}
return count;
}
const nums = [3, 1, 2, 2, 2, 1, 3];
const k = 2;
console.log(countPairs(nums, k));#include <stdio.h>
#include <string.h>
#define MAX 101
int countPairs(int* nums, int n, int k) {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] == nums[j] && (i * j) % k == 0) {
count++;
}
}
}
return count;
}
int main() {
int nums[] = {3, 1, 2, 2, 2, 1, 3};
int k = 2;
int length = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", countPairs(nums, length, k));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int CountPairs(int[] nums, int k) {
Dictionary<int, List<int>> indexMap = new Dictionary<int, List<int>>();
int count = 0;
for (int i = 0; i < nums.Length; i++) {
if (!indexMap.ContainsKey(nums[i])) {
indexMap[nums[i]] = new List<int>();
}
foreach (int index in indexMap[nums[i]]) {
if ((index * i) % k == 0) {
count++;
}
}
indexMap[nums[i]].Add(i);
}
return count;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {3, 1, 2, 2, 2, 1, 3};
int k = 2;
Console.WriteLine(sol.CountPairs(nums, k));
}
}The Python solution uses a defaultdict to map each number to the indices list where it appears. This provides a direct way to access potential pairs, reducing unnecessary checks.
Time Complexity: O(n * m), where m is average frequency list size.
Space Complexity: O(n), for storing indices in the dictionary.
Approach 3: Enumeration
We first enumerate the index j in the range [0, n), and then enumerate the index i in the range [0, j). We count the number of pairs that satisfy nums[i] = nums[j] and (i times j) bmod k = 0.
The time complexity is O(n^2), where n is the length of the array nums. The space complexity is O(1).
function countPairs(nums: number[], k: number): number {
let ans = 0;
for (let j = 1; j < nums.length; ++j) {
for (let i = 0; i < j; ++i) {
if (nums[i] === nums[j] && (i * j) % k === 0) {
++ans;
}
}
}
return ans;
}func countPairs(nums []int, k int) (ans int) {
for j, y := range nums {
for i, x := range nums[:j] {
if x == y && (i*j%k) == 0 {
ans++
}
}
}
return
}impl Solution {
pub fn count_pairs(nums: Vec<i32>, k: i32) -> i32 {
let mut ans = 0;
for j in 1..nums.len() {
for (i, &x) in nums[..j].iter().enumerate() {
if x == nums[j] && (i * j) as i32 % k == 0 {
ans += 1;
}
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2). |
| HashMap Frequency Counting Approach | Time Complexity: O(n * m), where m is average frequency list size. |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Check | O(n²) | O(1) | Best for understanding the problem logic or when the array size is small. |
| HashMap Frequency Grouping | O(n²) worst case | O(n) | Useful when the array has many distinct values and you want to avoid unnecessary pair checks. |
Frequently asked questions
Is Count Equal and Divisible Pairs in an Array easy or hard?
Count Equal and Divisible Pairs in an Array is categorized as an Easy problem. The brute force solution is straightforward with nested loops, while the HashMap optimization introduces a common interview technique for reducing unnecessary comparisons.
Count Equal and Divisible Pairs in an Array Python/Java solution
In Python and Java, the common implementation first builds a dictionary or HashMap mapping values to index lists. Then it iterates through each list and checks pairs (i, j) to verify whether (i * j) % k == 0 while maintaining i < j.
How to solve Count Equal and Divisible Pairs in an Array in O(n)?
An exact O(n) solution is not generally possible because the algorithm must potentially evaluate many index combinations that satisfy the equality condition. The typical optimization is to group indices by value using a HashMap and only evaluate pairs within each group, reducing unnecessary comparisons.
What is the best approach for Count Equal and Divisible Pairs in an Array?
The practical approach groups indices by value using a HashMap, then checks index pairs only within each group. This avoids comparing elements with different values. The worst-case time complexity remains O(n^2), but it performs much better when the array contains many distinct numbers.
Is Count Equal and Divisible Pairs in an Array asked at Google/Amazon/Meta?
Problems combining array iteration, hashing, and index-based conditions appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact question may vary, the underlying pattern of filtering pairs with hash maps and validating conditions is common.
What data structure is used in Count Equal and Divisible Pairs in an Array?
The optimized approach uses a HashMap (hash table) that maps each number to the list of indices where it appears. This structure allows you to process only indices with equal values instead of scanning the entire array repeatedly.
What is the time complexity of Count Equal and Divisible Pairs in an Array?
The straightforward brute force solution runs in O(n^2) time because it checks every pair of indices. The HashMap grouping approach also has O(n^2) worst-case time when all values are identical, with O(n) additional space for storing index groups.