Count Equal and Divisible Pairs in an Array
EasyPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward approach is to use brute force. We can iterate through every possible pair of indices (i, j) in the array such that i < j. For each pair, we check if it satisfies the two conditions given in the problem: nums[i] == nums[j] and (i * j) % k == 0. If both conditions hold true, we increment a counter.
Algorithm
- Initialize a counter
countto 0. - Use a nested loop to iterate through all pairs of indices
(i, j)such that0 <= i < j < n. - For each pair, check if
nums[i] == nums[j]. - If the values are equal, check if the product of indices
(i * j)is divisible byk. - If both conditions are met, increment the
count. - After iterating through all pairs, return
count.
Walkthrough
We initialize a counter variable, count, to zero. We then use a nested loop structure. The outer loop iterates with index i from 0 to n-2, and the inner loop iterates with index j from i + 1 to n-1, where n is the length of the array. This structure ensures that we only consider pairs (i, j) with i < j. Inside the inner loop, we check if nums[i] is equal to nums[j] and if the product (i * j) is divisible by k. If both conditions are met, we increment our count. After the loops complete, the count holds the total number of valid pairs.
class Solution { public int countPairs(int[] nums, int k) { int n = nums.length; int count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (nums[i] == nums[j] && (i * j) % k == 0) { count++; } } } return count; }}Complexity
Time
O(n^2), where `n` is the number of elements in `nums`. The nested loops iterate through all possible pairs `(i, j)` with `i < j`, resulting in approximately `n^2 / 2` comparisons.
Space
O(1), as we only use a few variables to store the count and loop indices, not dependent on the input size.
Trade-offs
Pros
Very simple to understand and implement.
Requires no additional memory, making its space complexity optimal.
Cons
Inefficient for large input sizes as it checks every possible pair of indices, regardless of their values.
Performs many unnecessary comparisons when the array contains many unique values.
A more optimized approach avoids checking pairs of indices with different values from the start. We can iterate through the array once, using a HashMap to keep track of the indices of each number encountered so far. For each element nums[i], we only need to check it against the previous occurrences of the same number. This significantly reduces the number of divisibility checks if the array has many unique values.
Algorithm
- Initialize a counter
count = 0and aHashMap<Integer, List<Integer>>namedmap. - Iterate through the
numsarray with indexifrom0ton-1. - For the current element
num = nums[i]:- If
mapcontainsnumas a key, retrieve its list of previously seen indices. - For each
prevIndexin that list, check if(i * prevIndex) % k == 0. - If the condition is true, increment
count. - Add the current index
ito the list of indices fornumin themap.
- If
- Return
count.
Walkthrough
This optimized method avoids redundant checks by grouping indices of equal-valued elements using a HashMap. We initialize a counter count to zero and a HashMap<Integer, List<Integer>> to map each number to a list of its indices. We iterate through the nums array from i = 0 to n-1. For each element nums[i], we look up its value in the map. If it's already present, we iterate through its list of previously seen indices (prevIndex). For each prevIndex, we check if (i * prevIndex) % k == 0. If it is, we increment count. Finally, we add the current index i to the list for nums[i] in the map. This ensures that for each i, we are only comparing it with j < i where nums[j] == nums[i].
import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map; class Solution { public int countPairs(int[] nums, int k) { int count = 0; Map<Integer, List<Integer>> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int num = nums[i]; if (map.containsKey(num)) { List<Integer> indices = map.get(num); for (int prevIndex : indices) { if ((long)i * prevIndex % k == 0) { count++; } } } map.computeIfAbsent(num, key -> new ArrayList<>()).add(i); } return count; }}Complexity
Time
O(n^2) in the worst case (when all elements are identical). However, it's much faster on average. If a number appears `c` times, we perform `c*(c-1)/2` checks for it. The total time is the sum of these checks over all unique numbers, which is generally much less than `n^2`.
Space
O(n) in the worst case. The HashMap stores at most `n` indices in total across all its lists.
Trade-offs
Pros
More efficient than brute force on average, as it only performs divisibility checks on pairs with equal values.
Reduces the total number of pairs to check, especially for arrays with high numbers of unique elements.
Cons
Requires extra space to store the HashMap, which can be up to O(n).
The worst-case time complexity is still O(n^2), which occurs if all elements in the array are the same.
Solutions
Solution
class Solution {public int countPairs(int[] nums, int k) { int n = nums.length; int ans = 0; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (nums[i] == nums[j] && (i * j) % k == 0) { ++ans; } } } return ans; }}class Solution {public: int countPairs(vector<int> &nums, int k) { int n = nums.size(); int ans = 0; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (nums[i] == nums[j] && (i * j) % k == 0) ++ans; } } return ans; }};class Solution: def countPairs(self, nums: List[int], k: int) -> int: n = len(nums) return sum(nums[i] == nums[j] and (i * j) % k == 0 for i in range(n) for j in range(i + 1, n))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.