Skip to main content
Talentd

Find the Number of Good Pairs I - Solution & Explanation

EasyArrayHash Table17 min readAsked at: Airbus
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given two integer arrays nums1 and nums2, along with an integer k. A pair (i, j) is considered good if nums1[i] is divisible by nums2[j] * k. The task is to count how many such pairs exist across both arrays.

Approach 1: Brute Force Pair Check (Time: O(n * m), Space: O(1))

The most direct strategy is to check every possible pair. Iterate through each element in nums1 and for each element iterate through nums2. For every pair, compute nums2[j] * k and check whether nums1[i] % (nums2[j] * k) == 0. If the condition holds, increment the count. This approach uses simple nested iteration over the two arrays and requires no additional data structures. It works well when the arrays are small, but performance degrades as their sizes grow because every combination must be evaluated.

Approach 2: Hash Table + Divisor Enumeration (Time: O(n * sqrt(V) + m), Space: O(m))

A more efficient strategy reduces repeated checks using a hash table. First build a frequency map of values in nums2. Then iterate through nums1. Only elements divisible by k can form valid pairs, so compute x = nums1[i] / k. The condition becomes finding values in nums2 that divide x. Instead of checking every element in nums2, enumerate all divisors of x up to sqrt(x). If a divisor exists in the frequency map, add its count. Also check the paired divisor x / d when it differs from d. This preprocessing step avoids scanning the entire second array for each element and replaces it with constant-time hash lookups.

The key insight is rewriting the divisibility condition. If nums1[i] % (nums2[j] * k) == 0, then nums2[j] must divide nums1[i] / k. Turning the problem into divisor matching allows efficient lookups using a hash map rather than repeated multiplication checks. This technique appears frequently in problems combining array traversal with factor relationships.

Recommended for interviews: Start with the brute force explanation because it demonstrates clear understanding of the pair condition. Then move to the hash-table optimization that transforms the divisibility rule and uses divisor enumeration. Interviewers typically expect this transition from O(n * m) scanning to a structure-assisted lookup that significantly reduces redundant comparisons.

Approach 1: Brute Force Approach

This approach involves iterating over every possible pair (i, j) using two nested loops. For each pair, we check whether 'nums1[i] % (nums2[j] * k) == 0'. If this condition is met, the pair (i, j) is counted as a 'good' pair.

This implementation creates a function that calculates the number of 'good' pairs by iterating over each element of nums1 and nums2. It checks the divisibility condition and counts the pairs that satisfy this condition.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m), where n is the length of nums1 and m is the length of nums2.
Space Complexity: O(1), as no additional space is used.

Try this approach in the editor →

Approach 2: Optimized Preprocessing Approach

In this approach, we preprocess the nums2 array by calculating and storing the product nums2[j] * k for each j to avoid recalculating it multiple times. This results in potentially reduced computation within the nested loops.

This Python implementation first preprocesses the nums2 array by computing each element times k and storing it in a list. It then iterates over nums1 and the preprocessed list to determine and count 'good' pairs.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n * m), as it still involves checking each element pairwise but avoids recomputation within the inner loop.
Space Complexity: O(m), where m is the length of nums2, for the preprocessed list.

Try this approach in the editor →

Approach 3: Brute Force Enumeration

We directly enumerate all digit pairs (x, y) and check whether x bmod (y times k) = 0. If it satisfies the condition, increment the answer by one.

After the enumeration is complete, return the answer.

The time complexity is O(m times n), where m and n are the lengths of arrays nums1 and nums2, respectively. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Hash Table + Enumerate Multiples

We use a hash table cnt1 to record the occurrence times of each number divided by k in array nums1, and a hash table cnt2 to record the occurrence times of each number in array nums2.

Next, we enumerate each number x in array nums2. For each number x, we enumerate its multiples y, where the range of y is [x, mx], where mx is the maximum key value in cnt1. Then we count the sum of cnt1[y], denoted as s. Finally, we add s times v to the answer, where v is cnt2[x].

The time complexity is O(n + m + (M / k) times log m), and the space complexity is O(n + m). Where n and m are the lengths of arrays nums1 and nums2 respectively, and M is the maximum value in array nums1.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n * m), where n is the length of nums1 and m is the length of nums2.
Space Complexity: O(1), as no additional space is used.

Optimized Preprocessing Approach

Time Complexity: O(n * m), as it still involves checking each element pairwise but avoids recomputation within the inner loop.
Space Complexity: O(m), where m is the length of nums2, for the preprocessed list.

Brute Force Enumeration—
Hash Table + Enumerate Multiples—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair CheckO(n * m)O(1)Best for small arrays or when implementing the simplest correct solution first
Hash Table + Divisor EnumerationO(n * sqrt(V) + m)O(m)General case optimization when nums1 values are large and repeated pair checks must be avoided

Video Solution

3164. Find the Number of Good Pairs II | Math | Factors | 3162. Find the Number of Good Pairs I • Aryan Mittal • 6,059 views views

Watch 7 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Find the Number of Good Pairs I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Array Pairs Divisible by K