Count Equal and Divisible Pairs in an Array

main.md

Question

Approach

I went through all possible pairs (i, j) where i < j, and for each pair, I checked if the elements at those indices were equal. If they were, I then checked whether i * j was divisible by k. If both conditions were true, I counted that pair as valid. After checking all pairs, I returned the total count.

Implementation

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

Complexities

• Time: O(n^2)
• Space: O(1)