2176. Count Equal and Divisible Pairs in an Array

Time: O(n²)

Space: O(n)

Intuition

Count pairs with same value and same absolute difference index. Group by value, then for each group count pairs with |i-j| divisible by... wait: pairs (i,j) where nums[i]==nums[j] and |i-j|%k==0.

Algorithm

1Group indices by value. For each group: count pairs with |i-j|%k==0.
2Equivalent to counting pairs with same (value, index%k). Use frequency map of (value, i%k).

Common Pitfalls

•Count pairs with same (nums[i], i%k) combination. Use map, count C(freq,2) for each key.

2176.cs

// Approach: Group indices by value; for each group check all index pairs if i*j divisible by k.
// Time: O(n²) Space: O(n)

public class Solution
{
    public int CountPairs(int[] nums, int k)
    {
        int ans = 0;
        Dictionary<int, List<int>> numToIndices = new Dictionary<int, List<int>>();

        for (int i = 0; i < nums.Length; ++i)
        {
            if (!numToIndices.ContainsKey(nums[i]))
                numToIndices[nums[i]] = new List<int>();

            numToIndices[nums[i]].Add(i);
        }

        foreach (List<int> indices in numToIndices.Values)
        {
            Dictionary<int, int> gcds = new Dictionary<int, int>();
            foreach (int i in indices)
            {
                int gcd_i = Gcd(i, k);
                foreach (int gcd_j in gcds.Keys)
                {
                    if (gcd_i * gcd_j % k == 0)
                        ans += gcds[gcd_j];
                }
                if (gcds.ContainsKey(gcd_i))
                    gcds[gcd_i]++;
                else
                    gcds[gcd_i] = 1;
            }
        }

        return ans;
    }

    private int Gcd(int a, int b)
    {
        return b == 0 ? a : Gcd(b, a % b);
    }
}

Was this solution helpful?