Find the Number of Good Pairs II - Practice Coding Problems

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

Understanding the Visualization

Input Arrays

nums1=[1,3,4], nums2=[1,3,4], k=1

Check Divisibility

For each nums1[i], check if divisible by nums2[j] * k

Count Valid Pairs

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

Key Takeaway

🎯 Key Insight: Use frequency counting to optimize repeated divisibility checks for duplicate values

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

Approach	Time	Space	Notes
✓ Frequency Count Optimization	O(n+m+u1×u2)	O(n+m)	Count frequencies to avoid redundant divisibility checks
Brute Force - Check All Pairs	O(n×m)	O(1)	Check every element in nums1 against every element in nums2

Frequency Count Optimization — Algorithm Steps

Step 1: Count frequency of each element in nums1 and nums2
Step 2: For each unique value in nums1, check divisibility against unique values in nums2
Step 3: Multiply frequencies to get total count of good pairs

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Build frequency maps for both arrays

Check Unique Pairs

Only check divisibility between unique values

Multiply Frequencies

Calculate total pairs by multiplying frequencies

Code -

solution.c — C

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

#define MAX_VAL 100000
int count1[MAX_VAL + 1] = {0};
int count2[MAX_VAL + 1] = {0};
int unique1[1000], unique2[1000];

int solution(int* nums1, int nums1Size, int* nums2, int nums2Size, int k) {
    memset(count1, 0, sizeof(count1));
    memset(count2, 0, sizeof(count2));
    
    int u1 = 0, u2 = 0;
    
    // Count frequencies and collect unique values
    for (int i = 0; i < nums1Size; i++) {
        if (count1[nums1[i]] == 0) {
            unique1[u1++] = nums1[i];
        }
        count1[nums1[i]]++;
    }
    
    for (int i = 0; i < nums2Size; i++) {
        if (count2[nums2[i]] == 0) {
            unique2[u2++] = nums2[i];
        }
        count2[nums2[i]]++;
    }
    
    int total = 0;
    for (int i = 0; i < u1; i++) {
        for (int j = 0; j < u2; j++) {
            if (unique1[i] % (unique2[j] * k) == 0) {
                total += count1[unique1[i]] * count2[unique2[j]];
            }
        }
    }
    return total;
}

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+u1×u2)

O(n+m) to count frequencies, O(u1×u2) to check unique pairs where u1,u2 are unique elements

✓ Linear Growth

Space Complexity

O(n+m)

Hash maps store frequency of each unique element from both arrays

⚡ Linearithmic 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Count Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler