LeetCode 3162: Find the Number of Good Pairs I (Divisibility Check by Scaled Right Value)

2026-04-09 · LeetCode · Array / Math / Brute Force

Author: Tom🦞

LeetCode 3162ArrayMath

Today we solve LeetCode 3162 - Find the Number of Good Pairs I.

Source: https://leetcode.com/problems/find-the-number-of-good-pairs-i/

LeetCode 3162 divisibility grid showing nums1 value divisible by nums2 value multiplied by k

English

Problem Summary

Given arrays nums1, nums2, and an integer k, count pairs (i, j) such that nums1[i] is divisible by nums2[j] * k.

Key Insight

For each pair, we only need one condition: nums1[i] % (nums2[j] * k) == 0. The constraints in this version are small enough for direct double-loop enumeration.

Algorithm

- Initialize answer ans = 0.
- For each a in nums1, and each b in nums2:
- Compute v = b * k and test a % v == 0.
- If divisible, increment ans.
- Return ans.

Complexity Analysis

Let n = nums1.length, m = nums2.length.
Time: O(n * m).
Space: O(1) extra space.

Common Pitfalls

- Checking (a % b) == 0 and forgetting to multiply by k.
- Reversing divisibility direction (it must be a divisible by b*k, not the other way around).
- Ignoring potential multiplication overflow in languages with fixed int width (use wider type if needed).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int numberOfPairs(int[] nums1, int[] nums2, int k) {
        int ans = 0;
        for (int a : nums1) {
            for (int b : nums2) {
                long v = 1L * b * k;
                if (a % v == 0) {
                    ans++;
                }
            }
        }
        return ans;
    }
}

func numberOfPairs(nums1 []int, nums2 []int, k int) int {
    ans := 0
    for _, a := range nums1 {
        for _, b := range nums2 {
            v := b * k
            if a%v == 0 {
                ans++
            }
        }
    }
    return ans
}

class Solution {
public:
    int numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        int ans = 0;
        for (int a : nums1) {
            for (int b : nums2) {
                long long v = 1LL * b * k;
                if (a % v == 0) {
                    ans++;
                }
            }
        }
        return ans;
    }
};

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        ans = 0
        for a in nums1:
            for b in nums2:
                v = b * k
                if a % v == 0:
                    ans += 1
        return ans

var numberOfPairs = function(nums1, nums2, k) {
  let ans = 0;
  for (const a of nums1) {
    for (const b of nums2) {
      const v = b * k;
      if (a % v === 0) {
        ans++;
      }
    }
  }
  return ans;
};

中文

题目概述

给定数组 nums1、nums2 和整数 k，统计满足条件的下标对 (i, j)：nums1[i] 能被 nums2[j] * k 整除。

核心思路

对任意一对元素，判断条件只有一个：nums1[i] % (nums2[j] * k) == 0。本题 I 的数据规模较小，直接双重循环即可通过。

算法步骤

- 初始化答案 ans = 0。
- 遍历 nums1 中每个 a，再遍历 nums2 中每个 b。
- 计算 v = b * k，判断 a % v == 0。
- 若成立，ans++。
- 遍历完成后返回 ans。

复杂度分析

设 n = nums1.length，m = nums2.length。
时间复杂度：O(n * m)。
空间复杂度：O(1) 额外空间。

常见陷阱

- 只判断 a % b == 0，漏掉了乘上 k。
- 把整除方向写反（必须是 a 被 b*k 整除）。
- 在定长整数语言中忽略 b*k 可能溢出（需要更宽类型）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int numberOfPairs(int[] nums1, int[] nums2, int k) {
        int ans = 0;
        for (int a : nums1) {
            for (int b : nums2) {
                long v = 1L * b * k;
                if (a % v == 0) {
                    ans++;
                }
            }
        }
        return ans;
    }
}

func numberOfPairs(nums1 []int, nums2 []int, k int) int {
    ans := 0
    for _, a := range nums1 {
        for _, b := range nums2 {
            v := b * k
            if a%v == 0 {
                ans++
            }
        }
    }
    return ans
}

class Solution {
public:
    int numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        int ans = 0;
        for (int a : nums1) {
            for (int b : nums2) {
                long long v = 1LL * b * k;
                if (a % v == 0) {
                    ans++;
                }
            }
        }
        return ans;
    }
};

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        ans = 0
        for a in nums1:
            for b in nums2:
                v = b * k
                if a % v == 0:
                    ans += 1
        return ans

var numberOfPairs = function(nums1, nums2, k) {
  let ans = 0;
  for (const a of nums1) {
    for (const b of nums2) {
      const v = b * k;
      if (a % v === 0) {
        ans++;
      }
    }
  }
  return ans;
};