Watch 10 video solutions for Count Equal and Divisible Pairs in an Array, a easy level problem involving Array. This walkthrough by codestorywithMIK has 6,304 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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[3], and 2 * 3 == 6, which is divisible by 2. - nums[2] == nums[4], and 2 * 4 == 8, 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], k = 1 Output: 0 Explanation: Since no value in nums is repeated, there are no pairs (i,j) that meet all the requirements.
Constraints:
1 <= nums.length <= 1001 <= nums[i], k <= 100Problem Overview: Given an integer array nums and an integer k, count pairs of indices (i, j) such that i < j, nums[i] == nums[j], and (i * j) % k == 0. The task combines value equality with an index divisibility condition, so you must track both the numbers and their positions.
Approach 1: Brute Force Pair Check (O(n²) time, O(1) space)
Iterate through every pair of indices using two nested loops. For each pair (i, j) where i < j, first check if the values are equal. If nums[i] == nums[j], compute (i * j) % k. When the result is zero, increment the pair count. This approach directly simulates the problem statement and works well for small arrays. Time complexity is O(n²) because every pair is examined, while space complexity remains O(1). Since the problem involves iterating through an array, this method is often the starting point during interviews to demonstrate baseline reasoning.
Approach 2: HashMap Frequency Grouping (O(n²) worst-case time, O(n) space)
Instead of comparing every pair in the array, group indices by their value using a HashMap<value, list of indices>. Iterate through the array once and store each index under its corresponding number. For each group of equal values, only evaluate pairs within that group because unequal numbers can never form valid pairs. Then check the divisibility condition (i * j) % k == 0 for index pairs inside the group. This reduces unnecessary comparisons when the array contains many distinct numbers. The time complexity remains O(n²) in the worst case (when all numbers are identical), but it is significantly faster in typical scenarios with mixed values. Space complexity is O(n) for the map. This method uses a hash table to organize data before processing, a common optimization pattern in array problems.
Recommended for interviews: Start with the brute force approach to show you understand the constraints and conditions clearly. Then move to the HashMap grouping technique to reduce unnecessary comparisons. Interviewers expect you to recognize that equality filtering can be done first using hashing, which demonstrates practical optimization skills even when the theoretical worst-case complexity remains O(n²).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Check | O(n²) | O(1) | Best for understanding the problem logic or when the array size is small. |
| HashMap Frequency Grouping | O(n²) worst case | O(n) | Useful when the array has many distinct values and you want to avoid unnecessary pair checks. |