Leetcode 3162: Find the Number of Good Pairs I

Input: The input consists of two integer arrays `nums1` and `nums2`, and a positive integer `k`.

Example: Example 1: Input: nums1 = [1,2,5], nums2 = [1,2,3], k = 2 Output: 4

Constraints:

• 1 <= n, m <= 50

• 1 <= nums1[i], nums2[j] <= 50

• 1 <= k <= 50

Output: Return the total number of good pairs, where each pair satisfies the divisibility condition.

Example: Example 1: Input: nums1 = [1,2,5], nums2 = [1,2,3], k = 2 Output: 4

Constraints:

• The output should be an integer representing the count of good pairs.

Goal: The goal is to identify all pairs (i, j) where `nums1[i]` is divisible by `nums2[j] * k`.

Steps:

• Iterate through each element in `nums1`.

• For each element in `nums1`, iterate through each element in `nums2`.

• Check if `nums1[i] % (nums2[j] * k) == 0`.

• Count each valid pair where the condition holds.

Goal: The input arrays and the integer `k` have the following constraints.

Steps:

• 1 <= n, m <= 50

• 1 <= nums1[i], nums2[j] <= 50

• 1 <= k <= 50

Assumptions:

• The arrays `nums1` and `nums2` will always have values between 1 and 50.

• The integer `k` will also be between 1 and 50.

• Input: Example 1:

• Explanation: For `nums1 = [1, 2, 5]`, `nums2 = [1, 2, 3]`, and `k = 2`, we have the following good pairs: - (0, 0) because `1 % (1 * 2) == 0` - (0, 1) because `1 % (2 * 2) == 0` - (1, 0) because `2 % (1 * 2) == 0` - (2, 1) because `5 % (2 * 2) == 0`.

Approach: The approach is straightforward: iterate over both arrays, check the divisibility condition, and count how many pairs satisfy the condition.

Observations:

• The condition involves checking divisibility of each element in `nums1` by the corresponding element in `nums2` multiplied by `k`.

• Since we are working with relatively small arrays (up to length 50), a double loop approach should be efficient enough.

Steps:

• Initialize a counter `res` to zero.

• Loop through all elements of `nums1` and `nums2`.

• For each pair `(i, j)`, check if `nums1[i] % (nums2[j] * k) == 0`.

• If the condition is true, increment `res`.

• Return `res` as the result.

Empty Inputs:

• Both `nums1` and `nums2` will never be empty.

Large Inputs:

• The solution should efficiently handle the maximum input size (n = 50, m = 50).

Special Values:

• Ensure the solution works when `k` is 1 or when `nums1[i]` and `nums2[j]` have values that are close to the upper limit of 50.

Constraints:

• Make sure the solution does not exceed the allowed time and space limits for the given constraints.

int numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
    
    int res = 0, m = nums1.size(), n = nums2.size();
    
    for(int i = 0; i < m; i++)
    for(int j = 0; j < n; j++)
        if(nums1[i] % (nums2[j] * k) == 0) res++;
    return res;
    
}

1 : Function Definition

int numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {

Defines the function 'numberOfPairs' that takes two vectors, 'nums1' and 'nums2', and an integer 'k', and returns the count of valid pairs.

2 : Variable Initialization

    int res = 0, m = nums1.size(), n = nums2.size();

Initializes the result variable 'res' to 0 and calculates the sizes of 'nums1' and 'nums2', storing them in 'm' and 'n', respectively.

3 : Outer Loop

    for(int i = 0; i < m; i++)

Starts the outer loop that iterates over each element of the vector 'nums1'.

4 : Inner Loop

    for(int j = 0; j < n; j++)

Starts the inner loop that iterates over each element of the vector 'nums2'.

5 : Condition Check

        if(nums1[i] % (nums2[j] * k) == 0) res++;

Checks if the element in 'nums1' at index 'i' is divisible by the product of the element in 'nums2' at index 'j' and 'k'. If true, increments the result counter 'res'.

6 : Return Statement

    return res;

Returns the value of 'res', which represents the total number of valid pairs found.

Best Case: O(n * m)

Average Case: O(n * m)

Worst Case: O(n * m)

Description: The time complexity is O(n * m), where `n` and `m` are the lengths of `nums1` and `nums2`, respectively.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1), as no extra space is used other than the input arrays and a counter.

Leetcode 3162: Find the Number of Good Pairs I

Explore →