LeetCode Entry

2176. Count Equal and Divisible Pairs in an Array

17.04.2025 easy 2025 kotlin rust

Pairs a[i] == b[j], i j % k == 0

2176. Count Equal and Divisible Pairs in an Array easy blog post substack youtube 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/961

Problem TLDR

Pairs a[i] == b[j], i * j % k == 0 #easy

Intuition

The brute force is accepted.

Approach

  • the problem has also more optimal solution by using gcd(i, k) * gcd(j, k) % k == 0 equality

Complexity

  • Time complexity: \(O(n^2)\)

  • Space complexity: \(O(1)\)

Code


    fun countPairs(nums: IntArray, k: Int) =
        nums.indices.sumOf { i ->
            (i + 1..<nums.size).count { j ->
                (i * j) % k == 0 && nums[i] == nums[j] }}



    pub fn count_pairs(n: Vec<i32>, k: i32) -> i32 {
        (0..n.len()).map(|i| (i + 1..n.len()).filter(|&j|
        (i * j) as i32 % k < 1 && n[i] == n[j]).count() as i32).sum()
    }



    int countPairs(vector<int>& n, int k) {
        int r = 0;
        for (int i = 0; i < size(n); ++i)
            for (int j = i + 1; j < size(n); ++j)
                r += i * j % k < 1 && n[i] == n[j];
        return r;
    }