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²).
This approach involves iterating over all possible pairs (i, j) using nested loops and checking if the conditions are met.
This code iterates over all pairs (i, j) where 0 <= i < j < n and checks if the elements are equal and i*j is divisible by k. The counter increment occurs whenever both conditions are satisfied.
Time Complexity: O(n^2).
Space Complexity: O(1), as only a constant amount of space is used.
Use a hashmap to count occurrences of elements. Check each pair using a single loop by jumping indices where same elements exist. This reduces the number of checks as repeated pairs can be calculated mathematically.
The C solution doesn't fully utilize the given approach of frequency counting, but similarly iterates through the pair calculations since hashmap isn't directly usable in C standard library.
Time Complexity: O(n^2).
Space Complexity: O(1).
We first enumerate the index j in the range [0, n), and then enumerate the index i in the range [0, j). We count the number of pairs that satisfy nums[i] = nums[j] and (i times j) bmod k = 0.
The time complexity is O(n^2), where n is the length of the array nums. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2). |
| HashMap Frequency Counting Approach | Time Complexity: O(n^2). |
| Enumeration | — |
| 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. |
Count Equal and Divisible Pairs in an Array | Brute Force | Optimal | Detailed Maths | Leetcode 2176 • codestorywithMIK • 6,304 views views
Watch 9 more video solutions →Practice Count Equal and Divisible Pairs in an Array with our built-in code editor and test cases.
Practice on FleetCode