Count Equal and Divisible Pairs in an Array — Solution
Count Equal and Divisible Pairs in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Count Equal and Divisible Pairs in an Array is an easy coding problem on arrays, asked in Amazon and Wipro interviews.
- Difficulty: Easy
- Topics: Arrays
- Asked at: Amazon, Wipro
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a 0-indexed integer 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.
Example 1
Input: nums = [3,1,2,2,2,1,3], k = 2
Output: 4
Explanation: The qualifying pairs are (0,6), (2,3), (2,4) and (3,4).
Example 2
Input: nums = [1,2,3,4], k = 1
Output: 0
Explanation: All values are distinct.
Example 3
Input: nums = [5,5,5], k = 2
Output: 3
Explanation: (0,1) and (0,2) have product 0, and (1,2) has product 2 — all divisible by 2.
Constraints
1 <= nums.length <= 1001 <= nums[i], k <= 100
Hints for Count Equal and Divisible Pairs in an Array
Hint 1
The array is short, so checking every pair is well within budget.
Hint 2
Both conditions must hold — equal values and
i * j % k == 0.Hint 3
Only pairs with
i < jcount, so the inner loop should start ati + 1.
How to solve Count Equal and Divisible Pairs in an Array
With n <= 100 the total pair count is at most 4950, so the direct double loop is the right tool — no cleverness required.
Approach
- Loop
iover all indices andjover indices afteri. - Count the pair when
nums[i] == nums[j]and(i * j) % k == 0. - Return the count.
Why it works
The double loop enumerates each unordered index pair exactly once, and both conditions are checked directly, so the count is exact by construction.
Complexity
- Time —
O(n²) - Space —
O(1)
Pitfalls
- Starting the inner loop at
0counts each pair twice and admitsi == j. i * juses indices, not values — a common misreading.- Index 0 pairs with everything as far as divisibility goes, since
0 * j == 0is divisible by anyk.
Reference solution
Python
from typing import List
def countPairs(nums: List[int], k: int) -> int:
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 countJava
public static 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;
}C++
int countPairs(vector<int>& nums, int k) {
int count = 0;
int n = (int) 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;
}JavaScript
var countPairs = function(nums, k) {
let count = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] === nums[j] && (i * j) % k === 0) count++;
}
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays