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.
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; }}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.