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

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

✓ Brute Force - Check All Pairs

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

For each element in nums1, check if it's divisible by each element in nums2 multiplied by k. Use nested loops to examine all possible pairs and count those where the divisibility condition holds.

Frequency Map Optimization

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

Count frequency of each unique value in nums2, then for each element in nums1, calculate how many elements in nums2 (multiplied by k) can divide it. This reduces redundant modulo operations when nums2 has duplicates.

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>
#include <ctype.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;
    
    // Read nums1
    fgets(line, sizeof(line), stdin);
    char* ptr = line;
    while (*ptr) {
        if (isdigit(*ptr)) {
            nums1[nums1Size++] = strtol(ptr, &ptr, 10);
        } else {
            ptr++;
        }
    }
    
    // Read nums2
    fgets(line, sizeof(line), stdin);
    ptr = line;
    while (*ptr) {
        if (isdigit(*ptr)) {
            nums2[nums2Size++] = strtol(ptr, &ptr, 10);
        } else {
            ptr++;
        }
    }
    
    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

Find the Number of Good Pairs I - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler