1import java.util.HashMap;
2import java.util.Map;
3import java.util.Collections;
4
5class Solution {
6    public long numberOfPairs(int[] nums1, int[] nums2, int k) {
7        // Map to store counts of elements in nums1 that are divisible by k.
8        Map<Integer, Integer> counts1 = new HashMap<>();
9        for (int num : nums1) {
10            if (num % k == 0) {
11                counts1.merge(num / k, 1, Integer::sum); // Increment count of num/k in the map.
12            }
13        }
14      
15        // If no element in nums1 is divisible by k, return 0.
16        if (counts1.isEmpty()) {
17            return 0;
18        }
19      
20        // Map to store counts of elements in nums2.
21        Map<Integer, Integer> counts2 = new HashMap<>();
22        for (int num : nums2) {
23            counts2.merge(num, 1, Integer::sum); // Increment count of num in the map.
24        }
25      
26        long result = 0;
27        // Find maximum key in counts1.
28        int maxKey = Collections.max(counts1.keySet());
29      
30        // Iterate over each entry in counts2.
31        for (Map.Entry<Integer, Integer> entry : counts2.entrySet()) {
32            int key = entry.getKey(); // Element from nums2.
33            int value = entry.getValue(); // Frequency of the element.
34            int sum = 0;
35          
36            // Iterate over multiples of 'key' in the possible range.
37            for (int multiple = key; multiple <= maxKey; multiple += key) {
38                sum += counts1.getOrDefault(multiple, 0); // Add counts from counts1 to sum.
39            }
40          
41            // Multiply frequency with sum to get the number of pairs contributed by this 'key'.
42            result += 1L * sum * value;
43        }
44      
45        // Return the computed result.
46        return result;
47    }
48}
49

1class Solution {
2public:
3    // Method to calculate the number of pairs based on provided conditions
4    long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
5        unordered_map<int, int> countDivisibles;  // Hashmap to count occurrences of elements divisible by k in nums1
6
7        // Traverse nums1 to count elements divisible by k
8        for (int num : nums1) {
9            if (num % k == 0) {  // Check if num is divisible by k
10                countDivisibles[num / k]++;  // Increment the count for num divided by k
11            }
12        }
13
14        // If there are no elements divisible by k, there cannot be any valid pairs
15        if (countDivisibles.empty()) {
16            return 0;
17        }
18
19        unordered_map<int, int> countNums2;  // Hashmap to count occurrences of each element in nums2
20
21        // Traverse nums2 to populate countNums2
22        for (int num : nums2) {
23            countNums2[num]++;  // Increment the count for each number
24        }
25
26        int maxValue = 0;  // Variable to store the maximum quotient found in countDivisibles
27
28        // Determine the maximum quotient from countDivisibles
29        for (auto& [quotient, _] : countDivisibles) {
30            maxValue = max(maxValue, quotient);
31        }
32
33        long long totalPairs = 0;  // Initialize total pairs counter
34
35        // Iterate through each element in nums2's count map
36        for (auto& [num, frequency] : countNums2) {
37            long long sum = 0;  // Initialize the sum of counts
38
39            // Compute the sum of possible divisible matches
40            for (int y = num; y <= maxValue; y += num) {
41                sum += countDivisibles[y];
42            }
43
44            // Multiply the sum with its frequency in nums2 to get the number of valid pairs for this element
45            totalPairs += sum * frequency;
46        }
47
48        return totalPairs;  // Return the total number of valid pairs
49    }
50};
51

1/**
2 * Function that calculates the number of valid pairs (i, j) such that nums1[i] is divisible by nums2[j] * k.
3 * 
4 * @param nums1 - Array of numbers for the first set of numbers.
5 * @param nums2 - Array of numbers for the second set of numbers.
6 * @param k - The divisor factor.
7 * @returns The number of valid pairs.
8 */
9function numberOfPairs(nums1: number[], nums2: number[], k: number): number {
10    // Create a map to store counts of elements from nums1 that are divisible by k.
11    const cnt1: Map<number, number> = new Map();
12
13    // Populate cnt1 with elements from nums1 that are divisible by k.
14    for (const num of nums1) {
15        if (num % k === 0) {
16            const key = (num / k) | 0;
17            cnt1.set(key, (cnt1.get(key) || 0) + 1);
18        }
19    }
20
21    // If no elements in nums1 are divisible by k, return 0.
22    if (cnt1.size === 0) {
23        return 0;
24    }
25
26    // Create a map to store counts of each number in nums2.
27    const cnt2: Map<number, number> = new Map();
28  
29    // Populate cnt2 with counts of elements from nums2.
30    for (const num of nums2) {
31        cnt2.set(num, (cnt2.get(num) || 0) + 1);
32    }
33  
34    // Find the maximum key in cnt1 to limit the search range.
35    const maxCnt1Key = Math.max(...cnt1.keys());
36
37    let totalPairs = 0;
38
39    // Iterate through each element in cnt2.
40    for (const [num2, count2] of cnt2) {
41        let subTotal = 0;
42
43        // Check multiples of num2 up to the maximum key in cnt1.
44        for (let multiple = num2; multiple <= maxCnt1Key; multiple += num2) {
45            subTotal += cnt1.get(multiple) || 0;
46        }
47
48        // Update the total with the product of subTotal and the count from cnt2.
49        totalPairs += subTotal * count2;
50    }
51
52    // Return the total number of valid pairs.
53    return totalPairs;
54}
55