#2644

Easy

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Find the Maximum Divisibility Score

Determine the divisor with the highest count of divisible elements in an array using a clear array-driven strategy.

Problem Statement

You are given two integer arrays, nums and divisors. For each integer in divisors, calculate how many elements in nums are divisible by it.

Return the integer from divisors that has the maximum divisibility score. If multiple integers share the maximum score, return the smallest one.

Examples

Example 1

Input: nums = [2,9,15,50], divisors = [5,3,7,2]

Output: 2

The divisibility score of divisors[0] is 2 since nums[2] and nums[3] are divisible by 5. The divisibility score of divisors[1] is 2 since nums[1] and nums[2] are divisible by 3. The divisibility score of divisors[2] is 0 since none of the numbers in nums is divisible by 7. The divisibility score of divisors[3] is 2 since nums[0] and nums[3] are divisible by 2. As divisors[0] , divisors[1] , and divisors[3] have the same divisibility score, we return the smaller one which is divisors[3] .

Example 2

Input: nums = [4,7,9,3,9], divisors = [5,2,3]

Output: 3

The divisibility score of divisors[0] is 0 since none of numbers in nums is divisible by 5. The divisibility score of divisors[1] is 1 since only nums[0] is divisible by 2. The divisibility score of divisors[2] is 3 since nums[2] , nums[3] and nums[4] are divisible by 3.

Example 3

Input: nums = [20,14,21,10], divisors = [10,16,20]

Output: 10

The divisibility score of divisors[0] is 2 since nums[0] and nums[3] are divisible by 10. The divisibility score of divisors[1] is 0 since none of the numbers in nums is divisible by 16. The divisibility score of divisors[2] is 1 since nums[0] is divisible by 20.

Constraints

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

Solution Approach

Brute-force counting

Iterate through each divisor and count the number of elements in nums divisible by it. Keep track of the divisor with the highest count and handle ties by choosing the smaller value.

Optimize with early tie-breaking

While counting divisibility scores, maintain the current maximum and update immediately when a higher score is found. If the score equals the current maximum, update only if the divisor is smaller.

Array-driven evaluation pattern

The core pattern is evaluating each divisor against the array systematically, ensuring all elements are considered and that the maximum score is identified reliably, highlighting the array-driven solution strategy.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

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

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Enumeration

We can enumerate each element $div$ in $divisors$, and calculate how many elements in $nums$ can be divided by $div$, denoted as $cnt$.

1

2

3

4

5

6

7

8

9

10

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

Continue Practicing

#2643 row with maximum ones #2646 minimize the total price of the trips #2640 find the score of all prefixes of an array