Count Equal and Divisible Pairs in an Array

Difficulty: Easy | Acceptance: 83.90% | Paid: No Topics: Array

Given a 0-indexed integer array 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.

• Examples
• Constraints
• Brute Force
• Hash Map Grouping

Examples

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[4] and 2 * 4 == 8, which is divisible by 2.
- nums[2] == nums[3] and 2 * 3 == 6, 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,5], k = 1
Output: 0
Explanation: Since there are no matching indices, the answer is 0.

Constraints

1 <= nums.length <= 100
1 <= nums[i] <= 100
1 <= k <= 100

Brute Force

Intuition Since the constraints are very small (n <= 100), we can simply iterate through every possible pair of indices (i, j) where i < j and check the conditions directly.

Steps

• Initialize a counter to 0.
• Iterate through the array with index i from 0 to n-1.
• Iterate through the array with index j from i+1 to n-1.
• Check if nums[i] == nums[j] and if (i * j) % k == 0.
• If both conditions are true, increment the counter.
• Return the counter.

class Solution:
    def countPairs(self, nums: list[int], k: int) -> int:
        n = len(nums)
        count = 0
        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

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Simple and effective given the small constraints.

Hash Map Grouping

Intuition We can optimize slightly by only checking pairs where the values are equal. We group indices by their values using a hash map, then only check pairs within each group.

Steps

• Create a hash map to store lists of indices for each unique number in nums.
• Iterate through the array and populate the map.
• Iterate through the values (lists of indices) in the map.
• For each list of indices, iterate through all pairs (p, q) where p < q.
• Check if (p * q) % k == 0.
• If true, increment the counter.
• Return the counter.

from collections import defaultdict

class Solution:
    def countPairs(self, nums: list[int], k: int) -> int:
        indices = defaultdict(list)
        for idx, val in enumerate(nums):
            indices[val].append(idx)
        
        count = 0
        for val, idx_list in indices.items():
            n = len(idx_list)
            for i in range(n):
                for j in range(i + 1, n):
                    if (idx_list[i] * idx_list[j]) % k == 0:
                        count += 1
        return count

Complexity

• Time: O(n²) in the worst case (if all elements are the same).
• Space: O(n) to store the hash map.
• Notes: Reduces checks when values are distinct, but complexity remains quadratic in the worst case.