We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Number of Good Pairs II

Difficulty: Medium

Problem 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. Return the total number of good pairs.

Key Insights

  • A good pair satisfies the condition nums1[i] % (nums2[j] * k) == 0.
  • The problem involves checking divisibility for each element in nums1 against each modified element in nums2.
  • Efficient counting can be achieved by using a hash map to precompute the values of nums2[j] * k.

Space and Time Complexity

Time Complexity: O(n * m)
Space Complexity: O(m)

Solution

To solve the problem, we will use a hash map to store the counts of each possible value of nums2[j] * k. This allows us to quickly determine how many elements in nums2 can divide each element in nums1. For each element in nums1, we will check how many times it is divisible by the values stored in the hash map.

  1. Create a hash map to store the frequency of each value of nums2[j] * k.
  2. Iterate through nums1 and for each element, calculate how many times it can be divided by the values in the hash map.
  3. Sum the counts to get the total number of good pairs.

Code Solutions

def countGoodPairs(nums1, nums2, k):
    from collections import defaultdict

    # Step 1: Create a frequency map for nums2[j] * k
    frequency_map = defaultdict(int)
    for num in nums2:
        frequency_map[num * k] += 1

    total_good_pairs = 0

    # Step 2: Count good pairs
    for num in nums1:
        for divisor in frequency_map:
            if num % divisor == 0:
                total_good_pairs += frequency_map[divisor]

    return total_good_pairs
← Back to All Questions