Count the number of index pairs whose values are equal and whose index product is divisible by a given integer.
Problem
Given an integer array nums and an integer k, count the number of pairs of indices (i, j) such that:
0 <= i < j < nums.lengthnums[i] == nums[j]i * jis divisible byk
Return the total number of such pairs.
Notes
- Indices are
0-based. - A pair is counted once, only for
i < j. - You may assume the array is not empty.
Intuition
The value constraint groups candidates by equal numbers, and the divisibility condition filters which index pairs inside each group are valid.
Input Format
- An integer array
nums - An integer
k
Output Format
- Return an integer: the number of valid pairs
(i, j)
Constraints
1 <= nums.lengthk >= 1nums[i]andkfit in standard integer ranges- Count only pairs with
i < j
Example 1
Input
nums = [3, 1, 2, 3, 1, 3], k = 3
Output
4
Explanation
Valid pairs are (0,3), (0,5), (3,5) for value 3, and (1,4) for value 1. Each of these has index product divisible by 3.
Example 2
Input
nums = [1, 2, 3, 4], k = 2
Output
0
Explanation
There are no equal-value pairs.
Show 1 more example
Example 3
Input
nums = [5, 5, 5], k = 2
Output
1
Explanation
The only pair with divisible index product is (1,2), since 1 * 2 = 2 is divisible by 2.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.