Problem Description

You are given two integer arrays, nums1 and nums2, and an integer k. Your task is to count the number of pairs (i, j) such that:

• 0 ≤ i < nums1.length
• 0 ≤ j < nums2.length
• nums1[i] * nums2[j] is divisible by k (i.e., nums1[i] * nums2[j] % k == 0)

Each pair (i, j) is counted separately, and you may use the same element from nums1 or nums2 multiple times (no restriction on reusing elements).

You need to return the total number of such valid pairs.

Thought Process

At first glance, the problem suggests checking every possible pair between nums1 and nums2. For each pair, we would multiply the elements and check if the product is divisible by k. This brute-force approach is straightforward but potentially inefficient for large input sizes.

To optimize, we observe that for a product a * b to be divisible by k, at least one of a or b must contribute the necessary factors of k. So, instead of blindly checking all pairs, we can precompute helpful information, such as the greatest common divisor (GCD) of nums1[i] and k, and use this to determine which elements in nums2 can form a valid pair with nums1[i].

This leads to the idea of grouping elements of nums2 by their GCD with k, and for each nums1[i], counting how many nums2[j] will satisfy the divisibility condition.

Solution Approach

Here’s how we can efficiently solve the problem:

1. Precompute GCDs: For each element a in nums1, compute gcd_a = gcd(a, k). Similarly, for each b in nums2, compute gcd_b = gcd(b, k).
2. Group and Count: Count the frequency of each gcd_b in nums2 using a hash map. This allows O(1) lookup for how many nums2[j] have a particular GCD with k.
3. Pairing Logic: For each a in nums1 (with gcd_a), iterate through all possible gcd_b values. The product a * b will be divisible by k if and only if gcd_a * gcd_b is divisible by k (since any factors missing from a must be provided by b).
4. Count Valid Pairs: For each a, sum up the counts of gcd_b in nums2 where (gcd_a * gcd_b) % k == 0.

This approach avoids the need to check every possible pair, reducing the time complexity significantly.

Example Walkthrough

Input: nums1 = [2, 3], nums2 = [6, 9], k = 6

1. Compute GCDs:
   For nums1:
   • gcd(2, 6) = 2
   • gcd(3, 6) = 3
   For nums2:
   • gcd(6, 6) = 6
   • gcd(9, 6) = 3
   So, nums2_gcd_count = {6: 1, 3: 1}
2. For a = 2 (gcd_a = 2):
   • Check gcd_b = 6: 2 * 6 = 12, 12 % 6 == 0 (valid, count = 1)
   • Check gcd_b = 3: 2 * 3 = 6, 6 % 6 == 0 (valid, count = 1)
   Total pairs for a = 2: 2
3. For a = 3 (gcd_a = 3):
   • Check gcd_b = 6: 3 * 6 = 18, 18 % 6 == 0 (valid, count = 1)
   • Check gcd_b = 3: 3 * 3 = 9, 9 % 6 == 3 (not valid)
   Total pairs for a = 3: 1
4. Final answer: 2 + 1 = 3

Time and Space Complexity

• Brute-force: For each element in nums1 and each in nums2, check divisibility. Time complexity is O(n * m), where n and m are lengths of nums1 and nums2.
• Optimized Approach:
  • Precompute GCDs: O(n + m)
  • For each nums1[i], iterate over all possible divisors of k (at most O(sqrt(k))), so total is O(n * d) where d is the number of divisors of k.
  • Space: O(m) for the hash map of nums2 GCD counts.

  In practice, this is much faster than the brute-force approach, especially when nums1 and nums2 are large.

Summary

By shifting from a brute-force check of all pairs to grouping by GCD and leveraging the properties of divisibility, we achieve a much more efficient solution. The key insight is that the product's divisibility by k depends on the GCDs of the elements with k. This allows us to count valid pairs with hash maps and simple arithmetic, making the solution both fast and elegant.

Code Implementation

from math import gcd
from collections import Counter

class Solution:
    def countPairs(self, nums1, nums2, k):
        count2 = Counter()
        for b in nums2:
            gb = gcd(b, k)
            count2[gb] += 1

        result = 0
        for a in nums1:
            ga = gcd(a, k)
            for gb in count2:
                if (ga * gb) % k == 0:
                    result += count2[gb]
        return result
      

#include <vector>
#include <unordered_map>
#include <numeric>
using namespace std;

class Solution {
public:
    int countPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        unordered_map<int, int> count2;
        for (int b : nums2) {
            int gb = gcd(b, k);
            count2[gb]++;
        }
        int result = 0;
        for (int a : nums1) {
            int ga = gcd(a, k);
            for (auto& [gb, freq] : count2) {
                if ((long long)ga * gb % k == 0) {
                    result += freq;
                }
            }
        }
        return result;
    }
};
      

import java.util.*;

class Solution {
    public int countPairs(int[] nums1, int[] nums2, int k) {
        Map<Integer, Integer> count2 = new HashMap<>();
        for (int b : nums2) {
            int gb = gcd(b, k);
            count2.put(gb, count2.getOrDefault(gb, 0) + 1);
        }
        int result = 0;
        for (int a : nums1) {
            int ga = gcd(a, k);
            for (int gb : count2.keySet()) {
                if ((long)ga * gb % k == 0) {
                    result += count2.get(gb);
                }
            }
        }
        return result;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }
}
      

function gcd(a, b) {
    while (b !== 0) {
        let t = b;
        b = a % b;
        a = t;
    }
    return a;
}

var countPairs = function(nums1, nums2, k) {
    let count2 = {};
    for (let b of nums2) {
        let gb = gcd(b, k);
        count2[gb] = (count2[gb] || 0) + 1;
    }
    let result = 0;
    for (let a of nums1) {
        let ga = gcd(a, k);
        for (let gb in count2) {
            if ((ga * gb) % k === 0) {
                result += count2[gb];
            }
        }
    }
    return result;
};