1. Count Equal and Divisible Pairs in an Array (LeetCode)
Model answer
The task
Count pairs of indices i < j whose array values are equal and whose index product is divisible by k.
Key idea
Check each possible pair once. A pair counts only when both its values match and i * j is divisible by k.
Approach
- Initialize a counter to zero.
- For each index
i, visit every later indexj. - Increment the counter when the values match and
i * jhas remainder zero upon division byk. - Return the counter.
from typing import List
class Solution:
def countPairs(self, nums: List[int], k: int) -> int:
count = 0
# Each pair is considered exactly once, with i < j.
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] == nums[j] and (i * j) % k == 0:
count += 1
return count
Complexity:
- Time: O(n²), checking each pair of indices once.
- Space: O(1), using only a counter and loop variables.
Common follow-ups
- Can this be faster for large arrays? Group indices by value, then count qualifying index pairs within each group; the worst case remains quadratic.
- Does the method handle negative array values? Yes; equality comparison works the same, and the divisibility test applies only to indices.
- What if
kis zero? The divisibility test is undefined, so the input must require a positivekor specify a different rule.