3164. Find the Number of Good Pairs II

Description

You are given 2 integer arrays nums1 and nums2 of lengths n and m respectively. You are also given a positive integer k.

A pair (i, j) is called good if nums1[i] is divisible by nums2[j] * k (0 <= i <= n - 1, 0 <= j <= m - 1).

Return the total number of good pairs.

 

Example 1:

Input: nums1 = [1,3,4], nums2 = [1,3,4], k = 1

Output: 5

Explanation:

The 5 good pairs are (0, 0), (1, 0), (1, 1), (2, 0), and (2, 2).

Example 2:

Input: nums1 = [1,2,4,12], nums2 = [2,4], k = 3

Output: 2

Explanation:

The 2 good pairs are (3, 0) and (3, 1).

 

Constraints:

• 1 <= n, m <= 105
• 1 <= nums1[i], nums2[j] <= 106
• 1 <= k <= 103

Solutions

Solution 1: Hash Table + Enumerate Multiples

We use a hash table cnt1 to record the occurrence times of each number divided by \(k\) in array nums1, and a hash table cnt2 to record the occurrence times of each number in array nums2.

Next, we enumerate each number \(x\) in array nums2. For each number \(x\), we enumerate its multiples \(y\), where the range of \(y\) is \([x, \textit{mx}]\), where mx is the maximum key value in cnt1. Then we count the sum of cnt1[y], denoted as \(s\). Finally, we add \(s \times v\) to the answer, where \(v\) is cnt2[x].

The time complexity is \(O(n + m + (M / k) \times \log m)\), and the space complexity is \(O(n + m)\). Where \(n\) and \(m\) are the lengths of arrays nums1 and nums2 respectively, and \(M\) is the maximum value in array nums1.

Python3JavaC++GoTypeScript

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        cnt1 = Counter(x // k for x in nums1 if x % k == 0)
        if not cnt1:
            return 0
        cnt2 = Counter(nums2)
        ans = 0
        mx = max(cnt1)
        for x, v in cnt2.items():
            s = sum(cnt1[y] for y in range(x, mx + 1, x))
            ans += s * v
        return ans

class Solution {
    public long numberOfPairs(int[] nums1, int[] nums2, int k) {
        Map<Integer, Integer> cnt1 = new HashMap<>();
        for (int x : nums1) {
            if (x % k == 0) {
                cnt1.merge(x / k, 1, Integer::sum);
            }
        }
        if (cnt1.isEmpty()) {
            return 0;
        }
        Map<Integer, Integer> cnt2 = new HashMap<>();
        for (int x : nums2) {
            cnt2.merge(x, 1, Integer::sum);
        }
        long ans = 0;
        int mx = Collections.max(cnt1.keySet());
        for (var e : cnt2.entrySet()) {
            int x = e.getKey(), v = e.getValue();
            int s = 0;
            for (int y = x; y <= mx; y += x) {
                s += cnt1.getOrDefault(y, 0);
            }
            ans += 1L * s * v;
        }
        return ans;
    }
}

class Solution {
public:
    long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        unordered_map<int, int> cnt1;
        for (int x : nums1) {
            if (x % k == 0) {
                cnt1[x / k]++;
            }
        }
        if (cnt1.empty()) {
            return 0;
        }
        unordered_map<int, int> cnt2;
        for (int x : nums2) {
            ++cnt2[x];
        }
        int mx = 0;
        for (auto& [x, _] : cnt1) {
            mx = max(mx, x);
        }
        long long ans = 0;
        for (auto& [x, v] : cnt2) {
            long long s = 0;
            for (int y = x; y <= mx; y += x) {
                s += cnt1[y];
            }
            ans += s * v;
        }
        return ans;
    }
};

func numberOfPairs(nums1 []int, nums2 []int, k int) (ans int64) {
    cnt1 := map[int]int{}
    for _, x := range nums1 {
        if x%k == 0 {
            cnt1[x/k]++
        }
    }
    if len(cnt1) == 0 {
        return 0
    }
    cnt2 := map[int]int{}
    for _, x := range nums2 {
        cnt2[x]++
    }
    mx := 0
    for x := range cnt1 {
        mx = max(mx, x)
    }
    for x, v := range cnt2 {
        s := 0
        for y := x; y <= mx; y += x {
            s += cnt1[y]
        }
        ans += int64(s) * int64(v)
    }
    return
}

function numberOfPairs(nums1: number[], nums2: number[], k: number): number {
    const cnt1: Map<number, number> = new Map();
    for (const x of nums1) {
        if (x % k === 0) {
            cnt1.set((x / k) | 0, (cnt1.get((x / k) | 0) || 0) + 1);
        }
    }
    if (cnt1.size === 0) {
        return 0;
    }
    const cnt2: Map<number, number> = new Map();
    for (const x of nums2) {
        cnt2.set(x, (cnt2.get(x) || 0) + 1);
    }
    const mx = Math.max(...cnt1.keys());
    let ans = 0;
    for (const [x, v] of cnt2) {
        let s = 0;
        for (let y = x; y <= mx; y += x) {
            s += cnt1.get(y) || 0;
        }
        ans += s * v;
    }
    return ans;
}

Comments