Problem Description

You are given two integer arrays, nums1 and nums2, with lengths n and m, respectively. You also have a positive integer k. A pair (i, j) is considered "good" if the element nums1[i] from the first array is divisible by the product of nums2[j] and k. Indices i range from 0 to n-1, and indices j range from 0 to m-1. The task is to find the total number of such "good" pairs.

Intuition

To solve the problem, you can use a simple strategy: iterate through every possible pair of elements from nums1 and nums2. For each combination (x, y), check whether x % (y * k) == 0, which means x is perfectly divisible by y multiplied by k. If this condition holds true, it means the pair (i, j) is "good" and contributes to the count. This is an exhaustive search approach that checks each pair without any optimization but is straightforward to implement for a smaller range of input sizes.

Solution Approach

Solution 1: Brute Force Enumeration

The solution uses a straightforward brute force enumeration method to find the "good" pairs:

1. Nested Iteration: The algorithm iterates through each element x in nums1 and each element y in nums2.
2. Condition Check: For every pair (x, y), it checks if the condition x % (y * k) == 0 is satisfied, which means x is divisible by the product of y and k.
3. Counting Good Pairs: If the condition is true, it increments a counter to keep track of the number of "good" pairs.
4. Summation: The algorithm utilizes a generator expression within the sum() function to execute the above logic concisely. The expression iterates over each pair and yields True values interpreted as 1 for pairs meeting the condition.

The Python implementation is encapsulated in the numberOfPairs method, leveraging Python's functional capabilities for compactness and clarity:

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        return sum(x % (y * k) == 0 for x in nums1 for y in nums2)

This brute force approach is simple and effective for small input sizes, ensuring all potential pairings are considered without missing any potential "good" pairs.

Example Walkthrough

To illustrate the solution approach, let's consider a small example:

• nums1 = [4, 9]
• nums2 = [1, 2]
• k = 2

We need to find the total number of "good" pairs (i, j) where nums1[i] is divisible by nums2[j] * k.

1. Initialize Counters: Start with a count of 0 for keeping track of "good" pairs.

2. Iterate Over Pairs:

   • For i = 0, nums1[0] = 4:

     • For j = 0, nums2[0] = 1:
       • Check if 4 % (1 * 2) == 0:
         • Calculation: 4 % 2 == 0 is true, so this is a "good" pair.
         • Increment count: count = 1.
     • For j = 1, nums2[1] = 2:
       • Check if 4 % (2 * 2) == 0:
         • Calculation: 4 % 4 == 0 is true, so this is also a "good" pair.
         • Increment count: count = 2.

   • For i = 1, nums1[1] = 9:

     • For j = 0, nums2[0] = 1:
       • Check if 9 % (1 * 2) == 0:
         • Calculation: 9 % 2 == 0 is false, not a "good" pair.
     • For j = 1, nums2[1] = 2:
       • Check if 9 % (2 * 2) == 0:
         • Calculation: 9 % 4 == 0 is false, not a "good" pair.

3. Final Count: The total count of "good" pairs is 2.

Through this example, the brute force approach iterates through all possible pairs and checks the divisibility condition, incrementing the counter for every "good" pair found. This process ensures that the solution captures all valid pairings.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(m * n), where m and n are the lengths of the arrays nums1 and nums2, respectively. This is because the code uses a nested loop to iterate over each element in nums1 and nums2, resulting in a total of m * n iterations. Each iteration performs a modulus operation and a comparison, both of which can be considered O(1) operations.

The space complexity is O(1) since no additional space is used that scales with the size of the input arrays. The only extra space used is for a few variables, which is constant in size.

Learn more about how to find time and space complexity quickly.