Count Equal and Divisible Pairs in an Array

Leetcode Problem:

• Count Equal and Divisible Pairs in an Array

Summary

• Given an integer array and an integer k, return the number of pairs where the product of indices is divisible by k.

Approach

• The approach is to use two nested loops to generate all possible pairs of indices in the array
• For each pair, we check if the elements at those indices are equal and if their product is divisible by k
• If both conditions are met, we increment the answer counter.

Complexity

• O(n^2) where n is the length of the input array

Explanation

• The time complexity is O(n^2) because we have two nested loops that iterate over the array
• The space complexity is O(1) because we only use a constant amount of space to store the answer and other variables.

Solution Code:

class Solution {
public:
    int countPairs(vector& nums, int k) {
        int ans = 0;
        for(int i = 0 ; i < nums.size(); i++){
            for(int j = i + 1; j < nums.size(); j++){
                if(nums[i] != nums[j]) continue;
                if((i*j)%k != 0) continue;
                ans++;
            }
        }
        return ans;
    }
};