Is Find the Number of Good Pairs I easy or hard?

Find the Number of Good Pairs I is classified as an Easy problem with an acceptance rate around 86%. The brute force solution is straightforward, while the optimized version introduces hash tables and divisor logic for better performance.

Find the Number of Good Pairs I Python/Java solution

In Python or Java, the brute force implementation uses two nested loops to check nums1[i] % (nums2[j] * k) == 0. The optimized version stores nums2 frequencies in a dictionary or HashMap and checks divisors of nums1[i] / k to count valid matches efficiently.

How to solve Find the Number of Good Pairs I in O(n)?

Strict O(n) is generally not achievable due to divisor checks. The closest practical optimization uses a hash table for nums2 and only processes nums1 values divisible by k. Divisor enumeration limits checks to sqrt(x) instead of scanning the entire second array.

What is the best approach for Find the Number of Good Pairs I?

The most efficient approach uses a hash table for nums2 and divisor enumeration for values derived from nums1. After filtering nums1 elements divisible by k, compute x = nums1[i] / k and check its divisors against the hash map. This reduces repeated pair checks and runs in about O(n * sqrt(V) + m) time instead of O(n * m).

Is Find the Number of Good Pairs I asked at Google/Amazon/Meta?

Problems combining array iteration with hash-table frequency counting appear frequently in interviews at companies like Amazon, Google, and Meta. Variants of divisibility or pair-counting problems are commonly used to test understanding of hash maps and optimization from brute force solutions.

What data structure is used in Find the Number of Good Pairs I?

The optimized solution relies on a hash table (or dictionary) to store the frequency of elements in nums2. This allows constant-time lookups when checking whether divisors of nums1[i] / k exist in the second array.

What is the time complexity of Find the Number of Good Pairs I?

The brute force approach runs in O(n * m) time because every pair between nums1 and nums2 is tested. An optimized method builds a frequency map for nums2 and enumerates divisors of nums1[i] / k, leading to roughly O(n * sqrt(V) + m) time where V is the maximum value in nums1.

Description Hints 1 Solution Video 12:51

3162. Find the Number of Good Pairs I

Easy86.4% acceptance1 company

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.

Example 1:

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:

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

Asked at 1 company

Airbus

Topics

Array Hash Table

Hints open one at a time

Hint 1

The constraints are small. Check all pairs.

12:51

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution