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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Number of Good Pairs I

Number: 3446

Difficulty: Easy

Paid? No

Companies: Airbus SE

Problem Description

You are given two integer arrays nums1 and nums2 along with a positive integer k. A pair (i, j) is called good if nums1[i] is divisible by (nums2[j] * k). Your task is to count and return the number of good pairs.

Key Insights

  • Since the input sizes are relatively small (each array can have at most 50 elements), a brute-force approach is acceptable.
  • Use nested loops to iterate through every pair of elements from nums1 and nums2.
  • Check whether nums1[i] is divisible by (nums2[j] * k).

Space and Time Complexity

Time Complexity: O(n * m), where n = length of nums1 and m = length of nums2.
Space Complexity: O(1)

Solution

We utilize two nested loops to traverse every combination of elements from nums1 and nums2. For each pair, check if the element from nums1 is divisible by the product of the corresponding element from nums2 and k. If the condition is met, increment a counter. Finally, return the counter as the total number of good pairs.

Code Solutions

# Python solution for "Find the Number of Good Pairs I"

def count_good_pairs(nums1, nums2, k):
    # Initialize the counter for good pairs.
    good_pairs_count = 0
    
    # Iterate over each number in nums1.
    for num in nums1:
        # Iterate over each number in nums2.
        for divisor in nums2:
            # Check if num is divisible by divisor * k.
            if num % (divisor * k) == 0:
                # Increment the counter of good pairs.
                good_pairs_count += 1
                
    # Return the total count of good pairs.
    return good_pairs_count

# Example usage:
print(count_good_pairs([1, 3, 4], [1, 3, 4], 1))  # Output: 5
← Back to All Questions