Find the Number of Good Pairs II - 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 (where 0 <= i <= n - 1 and 0 <= j <= m - 1).

Return the total number of good pairs.

Input & Output

Example 1 — Basic Case

$ Input: nums1 = [1,3,4], nums2 = [1,3,4], k = 1

› Output: 5

💡 Note: Good pairs: (0,0) since 1%(1*1)=0, (1,0) since 3%(1*1)=0, (1,1) since 3%(3*1)=0, (2,0) since 4%(1*1)=0, (2,2) since 4%(4*1)=0. Total = 5 pairs.

Example 2 — With Multiplier k=2

$ Input: nums1 = [1,2,4,12], nums2 = [2,4], k = 3

› Output: 2

💡 Note: Check divisibility by nums2[j]*k: nums2*3 = [6,12]. Only 12%6=0 and 12%12=0 are valid. Good pairs: (3,0) and (3,1). Total = 2 pairs.

Example 3 — No Valid Pairs

$ Input: nums1 = [1,3], nums2 = [5], k = 2

› Output: 0

💡 Note: nums2*k = [10]. Neither 1%10=1 nor 3%10=3 equals 0. No good pairs exist.

Constraints

1 ≤ nums1.length, nums2.length ≤ 10⁵
1 ≤ nums1[i], nums2[i] ≤ 10⁶
1 ≤ k ≤ 10³

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to count frequency of duplicate values to avoid redundant divisibility checks. Frequency count approach is optimal: build hash maps for both arrays, then check divisibility only between unique values and multiply by their frequencies. Time: O(n+m+u1×u2), Space: O(n+m)

Common Approaches

✓ Brute Force - Check All Pairs

⏱️ Time: O(n×m) Space: O(1)

For each element in nums1, iterate through all elements in nums2 and check if nums1[i] is divisible by nums2[j] * k. Count all valid pairs.

Frequency Count Optimization

⏱️ Time: O(n+m+u1×u2) Space: O(n+m)

Instead of checking each pair individually, count the frequency of each unique value in both arrays. Then for each unique value in nums1, check divisibility against unique values in nums2 and multiply by their frequencies.

Brute Force - Check All Pairs — Algorithm Steps

Step 1: Iterate through each element in nums1
Step 2: For each nums1[i], iterate through all elements in nums2
Step 3: Check if nums1[i] % (nums2[j] * k) == 0 and increment counter

Visualization

Tap to expand

Step-by-Step Walkthrough

Check First Element

nums1[0] = 1 against all nums2 elements

Check Second Element

nums1[1] = 3 against all nums2 elements

Count Valid Pairs

Sum all pairs where nums1[i] % (nums2[j] * k) == 0

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums1, int nums1Size, int* nums2, int nums2Size, int k) {
    int count = 0;
    for (int i = 0; i < nums1Size; i++) {
        for (int j = 0; j < nums2Size; j++) {
            if (nums1[i] % (nums2[j] * k) == 0) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    char line[10000];
    int nums1[1000], nums2[1000];
    int nums1Size = 0, nums2Size = 0, k;
    
    // Parse nums1
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9' || token[0] == '-') {
            nums1[nums1Size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    // Parse nums2
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9' || token[0] == '-') {
            nums2[nums2Size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    // Parse k
    scanf("%d", &k);
    
    printf("%d\n", solution(nums1, nums1Size, nums2, nums2Size, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

Nested loops iterate n×m times to check all pairs

✓ Linear Growth

Space Complexity

O(1)

Only using variables for counting, no extra data structures

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Find the Number of Good Pairs II - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler