알고리즘

Count Equal and Divisible Pairs in an Array

짬뽕얼큰하게 2025. 4. 17. 21:19

Leetcode Problem:

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