# Count Equal and Divisible Pairs in an Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-equal-and-divisible-pairs-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/count-equal-and-divisible-pairs-in-an-array
**Data structures:** Array
**Companies:** [zeta suite](https://scaleengineer.com/companies/zeta-suite)
---
## Problem
Given a **0-indexed** integer array `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 <= 100`
* `1 <= nums[i], k <= 100`

# Approaches
## Brute Force Iteration
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.
**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.
**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.
### Explanation
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.
```java
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;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Use a nested loop to iterate through all pairs of indices `(i, j)` such that `0 <= 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 by `k`.
- If both conditions are met, increment the `count`.
- After iterating through all pairs, return `count`.

## Optimized Approach with HashMap
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.
**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.
**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.
### Explanation
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]`.
```java
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;
    }
}
```
### Algorithm
- Initialize a counter `count = 0` and a `HashMap<Integer, List<Integer>>` named `map`.
- Iterate through the `nums` array with index `i` from `0` to `n-1`.
- For the current element `num = nums[i]`:
  - If `map` contains `num` as a key, retrieve its list of previously seen indices.
  - For each `prevIndex` in that list, check if `(i * prevIndex) % k == 0`.
  - If the condition is true, increment `count`.
  - Add the current index `i` to the list of indices for `num` in the `map`.
- Return `count`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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))

```