# Count Array Pairs Divisible by K
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-array-pairs-divisible-by-k)
Canonical: https://scaleengineer.com/dsa/problems/count-array-pairs-divisible-by-k
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array
**Companies:** [PayPal](https://scaleengineer.com/companies/paypal)
---
## Problem
Given a **0-indexed** integer array `nums` of length `n` and an integer `k`, return _the **number of pairs**_ `(i, j)` _such that:_

* `0 <= i < j <= n - 1` _and_
* `nums[i] * nums[j]` _is divisible by_ `k`.

**Example 1:**

**Input:** nums = [1,2,3,4,5], k = 2
**Output:** 7
**Explanation:** 
The 7 pairs of indices whose corresponding products are divisible by 2 are
(0, 1), (0, 3), (1, 2), (1, 3), (1, 4), (2, 3), and (3, 4).
Their products are 2, 4, 6, 8, 10, 12, and 20 respectively.
Other pairs such as (0, 2) and (2, 4) have products 3 and 15 respectively, which are not divisible by 2.    

**Example 2:**

**Input:** nums = [1,2,3,4], k = 5
**Output:** 0
**Explanation:** There does not exist any pair of indices whose corresponding product is divisible by 5.

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i], k <= 105`

# Approaches
## Brute Force
The most straightforward way to solve this problem is to check every possible pair of elements in the array. This approach uses two nested loops to generate all pairs `(i, j)` such that `0 <= i < j < n`. For each pair, it computes their product and checks if it's divisible by `k`.
**Time:** O(N<sup>2</sup>) - Where N is the number of elements in `nums`. The nested loops result in a quadratic number of operations, as we check every possible pair. · **Space:** O(1) - We only use a constant amount of extra space for the counter and loop variables.
**Pros:** Simple to understand and implement.; Requires no extra space besides a few variables.
**Cons:** This approach is very slow and will result in a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints (N up to 10<sup>5</sup>).
### Explanation
This method involves a brute-force check of all possible pairs. The outer loop runs from the first element to the second-to-last element, and the inner loop runs from the element after the outer loop's current element to the last one. This ensures that every pair `(i, j)` with `i < j` is considered exactly once. Inside the inner loop, we perform the multiplication and the divisibility check. A counter is maintained to keep track of the number of valid pairs found.

```java
class Solution {
    public long countPairs(int[] nums, int k) {
        long count = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (((long) nums[i] * nums[j]) % k == 0) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Use a nested loop to iterate through all unique pairs of indices `(i, j)` where `i < j`.
- For each pair, calculate the product `p = (long)nums[i] * nums[j]`. It's important to cast to `long` to prevent potential integer overflow since `nums[i]` and `nums[j]` can be up to 10<sup>5</sup>.
- Check if the product `p` is divisible by `k` using the modulo operator: `p % k == 0`.
- If the product is divisible by `k`, increment the `count`.
- After checking all pairs, return the final `count`.

## Optimized Approach using GCD and Iterative Counting
A more optimized approach uses number theory, specifically the greatest common divisor (GCD). The core insight is that the condition `(a * b) % k == 0` is equivalent to `(gcd(a, k) * gcd(b, k)) % k == 0`. This allows us to only care about the GCD of each number with `k`, significantly reducing the problem's complexity since the number of divisors of `k` is much smaller than `k` itself.

This approach processes the array element by element. It maintains a frequency map of the GCDs of numbers encountered so far. For each new number, it checks against the stored GCDs to count new valid pairs.
**Time:** O(N * d(k)) - Where N is the length of `nums` and `d(k)` is the number of divisors of `k`. The outer loop runs N times, and the inner loop iterates through the keys of the map, which has at most `d(k)` entries. The GCD calculation takes O(log k). So, a more precise complexity is O(N * (log k + d(k))). · **Space:** O(d(k)) - Where `d(k)` is the number of divisors of `k`. The space is used for the `gcdFreq` map, which stores at most `d(k)` unique keys.
**Pros:** Significantly more efficient than the brute-force approach.; Correctly handles large inputs within the time limit.
**Cons:** While much better than brute force, it can be slightly less efficient than the final approach because for each element, it iterates through all unique GCDs found so far.
### Explanation
We iterate through the `nums` array, and for each element `num`, we calculate its GCD with `k`, let's call it `g1`. We then need to find how many previously seen numbers `prev_num` can form a valid pair with `num`. Based on the property `(num * prev_num) % k == 0 <=> (gcd(num, k) * gcd(prev_num, k)) % k == 0`, we can check this condition using the GCDs.

We maintain a frequency map, `gcdFreq`, where keys are GCDs and values are their counts. For the current `g1`, we iterate through all keys `g2` in `gcdFreq`. If `(g1 * g2) % k == 0`, we add the frequency of `g2` to our total pair count. Finally, we update the frequency of `g1` in the map to include the current number for subsequent calculations.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public long countPairs(int[] nums, int k) {
        long count = 0;
        Map<Integer, Integer> gcdFreq = new HashMap<>();
        for (int num : nums) {
            int g1 = gcd(num, k);
            for (Map.Entry<Integer, Integer> entry : gcdFreq.entrySet()) {
                int g2 = entry.getKey();
                int freq = entry.getValue();
                if (((long) g1 * g2) % k == 0) {
                    count += freq;
                }
            }
            gcdFreq.put(g1, gcdFreq.getOrDefault(g1, 0) + 1);
        }
        return count;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0 and a hash map `gcdFreq` to store the frequency of GCDs of numbers seen so far.
- Iterate through each number `num` in the `nums` array.
- For each `num`, calculate `g1 = gcd(num, k)`.
- Now, iterate through the existing entries `(g2, freq)` in the `gcdFreq` map. `g2` is the GCD of a previously seen number, and `freq` is how many times it has appeared.
- For each `g2`, check if the product of the GCDs is divisible by `k`: `(long)g1 * g2 % k == 0`. 
- If it is, it means the current `num` forms a valid pair with all `freq` previous numbers corresponding to `g2`. Add `freq` to the total `count`.
- After checking against all previous GCDs, update the frequency map for the current number's GCD: `gcdFreq.put(g1, gcdFreq.getOrDefault(g1, 0) + 1)`.
- Return the total `count`.

## Most Efficient Approach using GCD and Frequency Map
This is the most efficient approach. It refines the GCD-based method by separating the process into two main steps. First, it aggregates the frequencies of all `gcd(num, k)` values from the input array. Second, it uses this frequency map to calculate the total number of valid pairs directly, without iterating through the original array again for pair-wise checks. This avoids redundant computations found in the previous approach.
**Time:** O(N * log(k) + d(k)<sup>2</sup>) - The first step of building the frequency map takes O(N * log(k)). The second step of counting pairs takes O(d(k)<sup>2</sup>). Since N is much larger than d(k)<sup>2</sup> in the worst case, the overall complexity is dominated by the first step. · **Space:** O(d(k)) - Where `d(k)` is the number of divisors of `k`. Space is needed for the frequency map and the list of unique GCDs.
**Pros:** This is the most time-efficient solution for the given constraints.; It cleanly separates the logic of data processing and combinatorial counting.
**Cons:** The implementation is slightly more complex as it involves two distinct phases: data aggregation and pair counting.
### Explanation
The logic remains centered on the property that `(a * b) % k == 0` is equivalent to `(gcd(a, k) * gcd(b, k)) % k == 0`. 

First, we pass through the `nums` array once to build a frequency map `gcdFreq` of all `gcd(num, k)` values. This takes O(N log k) time.

Once we have this map, the problem is transformed into a combinatorial one: given a multiset of GCDs, how many pairs `(g1, g2)` satisfy `(g1 * g2) % k == 0`? We can solve this by iterating through the unique GCDs. For every pair of unique GCDs `(d1, d2)`, we check the divisibility condition. If it holds, we calculate how many pairs from the original `nums` array this corresponds to using the frequencies stored in `gcdFreq` and add it to our total count. This counting part has a complexity of O(d(k)<sup>2</sup>), where `d(k)` is the number of divisors of `k`.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public long countPairs(int[] nums, int k) {
        Map<Integer, Integer> gcdFreq = new HashMap<>();
        for (int num : nums) {
            int g = gcd(num, k);
            gcdFreq.put(g, gcdFreq.getOrDefault(g, 0) + 1);
        }

        long count = 0;
        List<Integer> divisors = new ArrayList<>(gcdFreq.keySet());
        for (int i = 0; i < divisors.size(); i++) {
            for (int j = i; j < divisors.size(); j++) {
                int d1 = divisors.get(i);
                int d2 = divisors.get(j);

                if (((long) d1 * d2) % k == 0) {
                    if (d1 == d2) {
                        long n = gcdFreq.get(d1);
                        count += n * (n - 1) / 2;
                    } else {
                        long n1 = gcdFreq.get(d1);
                        long n2 = gcdFreq.get(d2);
                        count += n1 * n2;
                    }
                }
            }
        }
        return count;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}
```
### Algorithm
- **Step 1: Compute GCD Frequencies**
  - Initialize a hash map `gcdFreq`.
  - Iterate through each `num` in the `nums` array.
  - Calculate `g = gcd(num, k)`.
  - Update the frequency of `g` in the map: `gcdFreq.put(g, gcdFreq.getOrDefault(g, 0) + 1)`.
- **Step 2: Count Pairs from Frequencies**
  - Initialize `count = 0`.
  - Create a list `divisors` containing the unique GCDs (the keys from `gcdFreq`).
  - Use a nested loop to iterate through all pairs of unique GCDs `(d1, d2)` from the `divisors` list, with the inner loop starting from the outer loop's index to avoid duplicate pairs and handle same-element pairs correctly.
  - For each pair `(d1, d2)`, check if `(long)d1 * d2 % k == 0`.
  - If the condition is met:
    - If `d1 == d2`, it means we are forming pairs from numbers that have the same GCD. If there are `n` such numbers, they form `n * (n - 1) / 2` pairs. Add this to `count`.
    - If `d1 != d2`, we are forming pairs between two different groups of numbers. If there are `n1` numbers with GCD `d1` and `n2` with GCD `d2`, they form `n1 * n2` pairs. Add this to `count`.
- Return the total `count`.