leetcodedaybyday - Beats 100% with C++ and Beats 98.69% with Python3
IntuitionThe goal is to count pairs of indices (i, j) such that:
nums[i] == nums[j] (the elements are the same).
(i * j) % k == 0 (the product of indices is div
# Intuition
The goal is to count pairs of indices `(i, j)` such that:
1. `nums[i] == nums[j]` (the elements are the same).
2. `(i * j) % k == 0` (the product of indices is divisible by `k`).

The naive approach uses two nested loops to evaluate all possible pairs, but it can be optimized using a dictionary to store indices of the same value and avoid redundant comparisons.

# Approach
### Brute Force (Nested Loops)
1. Iterate over all pairs `(i, j)` where \(i < j\).
2. For each pair, check:
   - If `nums[i] == nums[j]`.
   - If `(i * j) % k == 0`.
3. Increment the count for valid pairs.
4. Return the total count.

### Optimized Approach (Using a Dictionary)
1. Use a dictionary `d` to store lists of indices where each value in `nums` occurs.
2. Iterate through `nums`:
   - For the current value `n` at index `i`, check all previously stored indices of `n` in the dictionary.
   - For each index `idx`, check if `(idx * i) % k == 0`.
   - Add the current index `i` to the list of indices for `n` in the dictionary.
3. Return the total count.

# Complexity
- **Time Complexity**:
  - **Brute Force**:  
    Two nested loops iterate over all pairs, resulting in \(O(n^2)\), where \(n\) is the size of `nums`.
  - **Optimized Approach**:  
    Each index is processed once, and we check only relevant indices from the dictionary, resulting in \(O(n + m)\), where \(m\) is the number of valid checks.

- **Space Complexity**:
  - **Brute Force**:  
    Uses \(O(1)\) space.
  - **Optimized Approach**:  
    The dictionary stores indices for unique values in `nums`, resulting in \(O(n)\) space in the worst case.

# Code
### Brute Force Approach (C++) And Optimize Approach with Python3
```cpp []
class Solution {
public:
    int countPairs(vector<int>& nums, int k) {
        int count = 0;
        for (int i = 0; i < nums.size(); i++){
            for (int j = i + 1; j < nums.size(); j++){
                if (nums[i] == nums[j] && (i * j) % k == 0){
                    count++;
                }
            }
        }
        return count;
    }
};
```
```python3 []
class Solution:
    def countPairs(self, nums: List[int], k: int) -> int:
        # count = 0
        # for i in range(len(nums)):
        #     for j in range(i + 1,len(nums)):
        #         if nums[i] == nums[j] and (i * j) % k == 0:
        #             count += 1

        # return count

        d = defaultdict(list)
        count = 0
        for i, n in enumerate(nums):
            if n in d:
                for idx in d[n]:
                    if (idx * i) % k == 0:
                        count += 1
            d[n].append(i)
        return count
```


['C++', 'Python3']