Find the Number of Good Pairs I - Practice Coding Problems

Find the Number of Good Pairs I - 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

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

› Output: 2

💡 Note: We need nums1[i] divisible by nums2[j]*3. Check: 12%(2*3)=0 and 12%(4*3)=0. Only element 12 creates good pairs, giving us 2 total pairs: (3,0) and (3,1).

Example 3 — No Good Pairs

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

› Output: 0

💡 Note: Check divisibility: 1%(5*2)≠0, 1%(7*2)≠0, 3%(5*2)≠0, 3%(7*2)≠0. No elements in nums1 are divisible by any nums2[j]*k, so 0 good pairs.

Constraints

1 ≤ nums1.length, nums2.length ≤ 50
1 ≤ nums1[i], nums2[j] ≤ 50
1 ≤ k ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Two arrays nums1, nums2 and multiplier k

Process

Check divisibility: nums1[i] % (nums2[j] * k) == 0

Output

Count of all good pairs found

Key Takeaway

🎯 Key Insight: Use modulo operation to efficiently check if one number divides another

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use the modulo operator to efficiently check divisibility. For each element in nums1, test if it's divisible by each element in nums2 multiplied by k. The brute force approach with nested loops is optimal for this problem. Time: O(n × m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Pairs	O(n × m)	O(1)	Check every element in nums1 against every element in nums2 multiplied by k
Frequency Map Optimization	O(n × m)	O(m)	Use frequency counting to reduce redundant calculations for duplicate values

Brute Force - Check All Pairs — Algorithm Steps

Step 1: Initialize count to 0
Step 2: For each nums1[i], check against all nums2[j] * k
Step 3: If nums1[i] % (nums2[j] * k) == 0, increment count
Step 4: Return total count

Visualization

Tap to expand

Step-by-Step Walkthrough

Setup

Initialize arrays and multiplier k

Check Pairs

For each nums1[i], test divisibility by nums2[j] * k

Count

Increment counter when divisible

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

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

Nested loops: outer loop runs n times, inner loop runs m times

✓ Linear Growth

Space Complexity

O(1)

Only using a single counter variable, no extra data structures

✓ Linear Space

8.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

Brute Force - Check All Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler