What is the main idea behind finding the maximum divisibility score?

The goal is to count how many elements in nums are divisible by each divisor and return the one with the highest count.

How do I handle multiple divisors with the same maximum score?

Select the smallest divisor among those with the highest divisibility score to resolve ties.

Can this be optimized beyond brute-force?

For small arrays, brute-force works well. For very large ranges, additional number theory or hashing might reduce comparisons, but the array-driven pattern remains.

What is the expected time complexity?

The solution iterates through each divisor and each nums element, giving O(n * m) time complexity.

Which pattern does this problem illustrate?

It illustrates an array-driven solution pattern where each element in one array is evaluated against all elements in another array.

#2644

Easy

auto_awesome数组·driven

LeetCode 题解工作台

找出可整除性得分最大的整数

给你两个整数数组 nums 和 divisors 。 divisors[i] 的可整除性得分等于满足 nums[j] 能被 divisors[i] 整除的下标 j 的数量。返回可整除性得分最大的整数 divisors[i] 。如果有多个整数具有最大得分，则返回数值最小的一个。示例 1： …

数组

题目描述

给你两个整数数组 nums 和 divisors 。

divisors[i] 的 可整除性得分 等于满足 nums[j] 能被 divisors[i] 整除的下标 j 的数量。

返回 可整除性得分 最大的整数 divisors[i] 。如果有多个整数具有最大得分，则返回数值最小的一个。

示例 1：

输入：nums = [2,9,15,50], divisors = [5,3,7,2]

输出：2

解释：

divisors[0] 的可整除性分数为 2 因为 nums[2] 和 nums[3] 能被 5 整除。

divisors[1] 的可整除性分数为 2 因为 nums[1] 和 nums[2] 能被 3 整除。

divisors[2] 的可整除性分数为 0 因为 nums 中没有数字能被 7 整除。

divisors[3] 的可整除性分数为 2 因为 nums[0] 和 nums[3] 能够被 2 整除。

因为 divisors[0] 、divisor[1] 和 divisors[3] 有相同的可整除性分数，我们返回更小的那个 divisors[3]。

示例 2：

输入：nums = [4,7,9,3,9], divisors = [5,2,3]

输出：3

解释：

divisors[0] 的可整除性分数为 0 因为 nums 中没有数字能被 5 整除。

divisors[1] 的可整除性分数为 1 因为只有 nums[0] 能被 2 整除。

divisors[2] 的可整除性分数为 3 因为 nums[2] ，nums[3] 和 nums[4] 能被 3 整除。

示例 3：

输入：nums = [20,14,21,10], divisors = [10,16,20]

输出：10

解释：

divisors[0] 的可整除性分数为 2 因为 nums[0] 和 nums[3] 能被 10 整除。

divisors[1] 的可整除性分数为 0 因为 nums 中没有数字能被 16 整除。

divisors[2] 的可整除性分数为 1 因为 nums[0] 能被 20 整除。

因为 divisors[0] 的可整除性分数最大，我们返回 divisors[0]。

提示：

1 <= nums.length, divisors.length <= 1000
1 <= nums[i], divisors[i] <= 10⁹

lightbulb

解题思路

方法一：枚举

我们可以枚举 $divisors$ 中的每个元素 $div$ ，计算 $nums$ 中有多少个元素能被 $div$ 整除，记为 $cnt$ 。

如果 $cnt$ 大于当前最大的可整除性得分 $mx$ ，则更新 $mx = cnt$ ，并且更新 $ans = div$ 。
如果 $cnt$ 等于 $mx$ 并且 $div$ 小于 $ans$ ，则更新 $ans = div$ 。

最后返回 $ans$ 即可。

时间复杂度 $(m \times n)$ ，其中 $m$ 和 $n$ 分别是 $nums$ 和 $divisors$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maxDivScore(self, nums: List[int], divisors: List[int]) -> int:
        ans, mx = divisors[0], 0
        for div in divisors:
            cnt = sum(x % div == 0 for x in nums)
            if mx < cnt:
                mx, ans = cnt, div
            elif mx == cnt and ans > div:
                ans = div
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n * m) where n is the length of nums and m is the length of divisors since each divisor is compared to every element. Space complexity is O(1) beyond input storage, tracking only maximum score and current best divisor.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Looking for correct counting of divisible elements for each divisor.
question_mark
Check if ties are correctly broken by selecting the smallest divisor.
question_mark
Expect efficient iteration without unnecessary nested structures beyond array traversal.

warning

常见陷阱

外企场景

error
Forgetting to handle multiple divisors with the same maximum score.
error
Using unnecessary extra space instead of simple counters.
error
Skipping elements in nums or divisors leading to incorrect counts.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the maximum divisibility score when arrays contain negative numbers.
arrow_right_alt
Return all divisors that share the maximum divisibility score instead of just the smallest.
arrow_right_alt
Compute maximum divisibility scores for multiple nums arrays against the same divisors array.

help

常见问题

外企场景

继续练习

#2643 一最多的行 #2646 最小化旅行的价格总和 #2640 一个数组所有前缀的分数