Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A qualifying pair has two separate requirements: equal array values and an index product divisible by k. Since the array is small, directly testing each distinct index pair avoids unnecessary grouping machinery.

Approach

Enumerate i < j with nested loops. Increment the answer only when nums[i] == nums[j] and (i * j) % k == 0, then return the count. The product uses zero-based indices, not the equal values themselves. In particular, a matching pair involving index zero always passes the divisibility test because its index product is zero. Increasing index order prevents counting a pair twice.

class Solution:
    def countPairs(self, nums: List[int], k: int) -> int:
        n = len(nums)
        res = 0

        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] == nums[j] and i * j % k == 0:
                    res += 1

        return res

Complexity analysis

Let n = nums.length. Time: O(n^2) to test every index pair. Auxiliary space: O(1).