Count Equal and Divisible Pairs in an Array - Solution & Explanation
Problem Statement
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 <= 100
Approach Overview
Problem 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 1: Brute Force Approach
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.
Complexity
Time Complexity: O(n^2).
Space Complexity: O(1), as only a constant amount of space is used.
Approach 2: HashMap Frequency Counting Approach
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.
Complexity
Time Complexity: O(n^2).
Space Complexity: O(1).
Approach 3: Enumeration
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).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2). |
| HashMap Frequency Counting Approach | Time Complexity: O(n^2). |
| Enumeration | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Count Equal and Divisible Pairs in an Array | Brute Force | Optimal | Detailed Maths | Leetcode 2176 • codestorywithMIK • 6,405 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Equal and Divisible Pairs in an Array easy or hard?
Count Equal and Divisible Pairs in an Array Python/Java solution
How to solve Count Equal and Divisible Pairs in an Array in O(n)?
What is the best approach for Count Equal and Divisible Pairs in an Array?
Is Count Equal and Divisible Pairs in an Array asked at Google/Amazon/Meta?
What data structure is used in Count Equal and Divisible Pairs in an Array?
What is the time complexity of Count Equal and Divisible Pairs in an Array?
Ready to solve this problem?
Practice Count Equal and Divisible Pairs in an Array with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor