Problem

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.

Examples

Example 1

1
2
3
4
5
6
7
8


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

1
2
3
4
5
6
7
8


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 <= 50
  • 1 <= nums1[i], nums2[j] <= 50
  • 1 <= k <= 50

Solution

Method 1 – Brute Force with Modulo Check

Intuition

We need to count all pairs (i, j) such that nums1[i] is divisible by nums2[j] * k. Since the constraints are small, we can check every possible pair directly.

Approach

  1. Initialize a counter ans to 0.
  2. For each element in nums1, iterate through each element in nums2.
  3. For each pair (i, j), check if nums1[i] % (nums2[j] * k) == 0.
  4. If true, increment ans.
  5. Return ans after all pairs are checked.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        int ans = 0;
        for (int a : nums1) {
            for (int b : nums2) {
                if (a % (b * k) == 0) ans++;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func numberOfPairs(nums1 []int, nums2 []int, k int) int {
    ans := 0
    for _, a := range nums1 {
        for _, b := range nums2 {
            if a%(b*k) == 0 {
                ans++
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int numberOfPairs(int[] nums1, int[] nums2, int k) {
        int ans = 0;
        for (int a : nums1) {
            for (int b : nums2) {
                if (a % (b * k) == 0) ans++;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun numberOfPairs(nums1: IntArray, nums2: IntArray, k: Int): Int {
        var ans = 0
        for (a in nums1) {
            for (b in nums2) {
                if (a % (b * k) == 0) ans++
            }
        }
        return ans
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def numberOfPairs(self, nums1: list[int], nums2: list[int], k: int) -> int:
        ans = 0
        for a in nums1:
            for b in nums2:
                if a % (b * k) == 0:
                    ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn number_of_pairs(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> i32 {
        let mut ans = 0;
        for &a in &nums1 {
            for &b in &nums2 {
                if a % (b * k) == 0 {
                    ans += 1;
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    numberOfPairs(nums1: number[], nums2: number[], k: number): number {
        let ans = 0;
        for (const a of nums1) {
            for (const b of nums2) {
                if (a % (b * k) === 0) ans++;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n * m), where n and m are the lengths of nums1 and nums2, since we check every pair.
  • 🧺 Space complexity: O(1), as only a constant amount of extra space is used.