Count Array Pairs Divisible by K

• 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⁵.
• 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.

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.

1class Solution {2    public long countPairs(int[] nums, int k) {3        long count = 0;4        int n = nums.length;5        for (int i = 0; i < n; i++) {6            for (int j = i + 1; j < n; j++) {7                if (((long) nums[i] * nums[j]) % k == 0) {8                    count++;9                }10            }11        }12        return count;13    }14}

• 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.

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.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public long countPairs(int[] nums, int k) {6        long count = 0;7        Map<Integer, Integer> gcdFreq = new HashMap<>();8        for (int num : nums) {9            int g1 = gcd(num, k);10            for (Map.Entry<Integer, Integer> entry : gcdFreq.entrySet()) {11                int g2 = entry.getKey();12                int freq = entry.getValue();13                if (((long) g1 * g2) % k == 0) {14                    count += freq;15                }16            }17            gcdFreq.put(g1, gcdFreq.getOrDefault(g1, 0) + 1);18        }19        return count;20    }21 22    private int gcd(int a, int b) {23        while (b != 0) {24            int temp = b;25            b = a % b;26            a = temp;27        }28        return a;29    }30}

• 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.

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)²), where d(k) is the number of divisors of k.

1import java.util.ArrayList;2import java.util.HashMap;3import java.util.List;4import java.util.Map;5 6class Solution {7    public long countPairs(int[] nums, int k) {8        Map<Integer, Integer> gcdFreq = new HashMap<>();9        for (int num : nums) {10            int g = gcd(num, k);11            gcdFreq.put(g, gcdFreq.getOrDefault(g, 0) + 1);12        }13 14        long count = 0;15        List<Integer> divisors = new ArrayList<>(gcdFreq.keySet());16        for (int i = 0; i < divisors.size(); i++) {17            for (int j = i; j < divisors.size(); j++) {18                int d1 = divisors.get(i);19                int d2 = divisors.get(j);20 21                if (((long) d1 * d2) % k == 0) {22                    if (d1 == d2) {23                        long n = gcdFreq.get(d1);24                        count += n * (n - 1) / 2;25                    } else {26                        long n1 = gcdFreq.get(d1);27                        long n2 = gcdFreq.get(d2);28                        count += n1 * n2;29                    }30                }31            }32        }33        return count;34    }35 36    private int gcd(int a, int b) {37        while (b != 0) {38            int temp = b;39            b = a % b;40            a = temp;41        }42        return a;43    }44}