#2176

Easy

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Count Equal and Divisible Pairs in an Array

Given an array, count pairs of elements that are equal and their indices product is divisible by a given integer.

Problem Statement

Given an integer array nums and an integer k, your task is to count the number of pairs (i, j) where i < j, nums[i] == nums[j], and the product of their indices i * j is divisible by k.

The problem asks for a brute-force approach to check every pair of indices and test both the equality condition (nums[i] == nums[j]) and divisibility condition (i * j % k == 0).

Examples

Example 1

Input: nums = [3,1,2,2,2,1,3], k = 2

Output: 4

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

Since no value in nums is repeated, there are no pairs (i,j) that meet all the requirements.

Constraints

1 <= nums.length <= 100
1 <= nums[i], k <= 100

Solution Approach

Brute-force solution

A straightforward solution involves iterating over all pairs of indices (i, j) where i < j. For each pair, check if nums[i] == nums[j] and if i * j is divisible by k. This approach runs in O(n^2) time, where n is the length of the array.

Optimization considerations

Although the brute-force solution works, there may be opportunities for optimization if the input array size increases. You can explore methods like reducing the number of checks using hashing or segmenting the array based on divisibility rules.

Edge cases

Ensure that the solution handles edge cases where no pairs exist, or when all elements in the array are the same. Additionally, edge cases related to small or large values of k must be tested.

Complexity Analysis

Metric	Value
Time	O(n^2)
Space	O(1)

The time complexity of the brute-force solution is O(n^2) because we check all pairs of indices. The space complexity is O(1) as no additional space is used besides loop variables.

What Interviewers Usually Probe

Understanding how to handle pairs and divisibility checks can indicate a solid grasp of basic iteration and array manipulation.
The ability to discuss potential optimizations shows the candidate can think beyond brute-force solutions.
Evaluating edge cases reflects attention to detail and robustness in solution design.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check the condition i < j and mistakenly considering pairs where i >= j.
Overlooking divisibility by k when checking the pairs, leading to incorrect counts.
Not handling arrays with all distinct elements properly, where no pairs should meet the conditions.

Follow-up variants

What if the array is sorted? Can we optimize the solution by leveraging the order?
What if the value of k is large, can we use modular arithmetic to speed up the process?
How would the problem change if instead of indices, we were to check the product of values themselves?

FAQ

How do I approach the 'Count Equal and Divisible Pairs in an Array' problem?

Start by using a brute-force approach that checks all pairs of indices. Ensure both the equality condition and divisibility by k are satisfied.

What is the time complexity of the brute-force solution?

The time complexity is O(n^2) because the solution involves checking all pairs of indices in the array.

Are there optimization strategies for larger arrays?

Yes, optimization can be explored by using hash maps, segmenting the array, or reducing unnecessary checks based on divisibility rules.

How do I handle edge cases in this problem?

Consider arrays with no equal pairs, arrays where all elements are the same, and variations of k, ensuring all possible scenarios are covered.

What other problems have a similar pattern to 'Count Equal and Divisible Pairs in an Array'?

Problems involving pairwise comparisons and divisibility often require array-driven solutions, like finding pairs that satisfy certain mathematical conditions.

terminal

Solution

Solution 1: 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 $\textit{nums}[i] = \textit{nums}[j]$ and $(i \times j) \bmod k = 0$.

1

2

3

4

5

6

7

class Solution:
    def countPairs(self, nums: List[int], k: int) -> int:
        ans = 0
        for j, y in enumerate(nums):
            for i, x in enumerate(nums[:j]):
                ans += int(x == y and i * j % k == 0)
        return ans

Continue Practicing

#2179 count good triplets in an array #2172 maximum and sum of array #2171 removing minimum number of magic beans