Find the Maximum Divisibility Score — Easy Problem & Solution

Problem statement

The divisibility score of a candidate d is the number of entries in nums that d divides exactly.

Return the divisor with the highest score. If several tie, return the smallest of them.

Example 1

Input: nums = [4,7,9,3,9], divisors = [5,2,3]
Output: 3
Explanation: 3 divides 9, 3 and 9 for a score of 3, beating 2 (one hit) and 5 (none).

Example 2

Input: nums = [20,14,21,10], divisors = [5,7,5]
Output: 5
Explanation: 5 and 7 both score 2, so the smaller wins.

Example 3

Input: nums = [12], divisors = [10,16]
Output: 10
Explanation: Neither divides 12, so both score 0 and the smaller wins.

Constraints

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

How to solve Find the Maximum Divisibility Score

There is nothing clever to do: score each divisor directly and keep the best under the stated tie-break.

Approach

1. For each divisor d, count how many entries of nums satisfy x % d == 0.
2. Adopt d when its score beats the best so far, or ties it while being smaller.

Why it works

The comparison 'higher score, then smaller value' is a strict total order on the candidates, so a single sweep keeping the maximum under that order finds the unique answer.

Complexity

• Time — O(n · m)
• Space — O(1)

Pitfalls

• Initialising the best score to 0 rather than -1 makes an all-zero input return whichever divisor came first rather than the smallest.
• Duplicated divisors are harmless — they tie with themselves.

Reference solution

Python

from typing import List

def maxDivScore(nums: List[int], divisors: List[int]) -> int:
    best_div = 0
    best_score = -1
    for d in divisors:
        score = sum(1 for x in nums if x % d == 0)
        if score > best_score or (score == best_score and d < best_div):
            best_score = score
            best_div = d
    return best_div

JavaScript

var maxDivScore = function(nums, divisors) {
    var bestDiv = 0, bestScore = -1;
    for (var i = 0; i < divisors.length; i++) {
        var d = divisors[i], score = 0;
        for (var j = 0; j < nums.length; j++) {
            if (nums[j] % d === 0) score++;
        }
        if (score > bestScore || (score === bestScore && d < bestDiv)) { bestScore = score; bestDiv = d; }
    }
    return bestDiv;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy