LeetCode 2644 - Find the Maximum Divisibility Score

The problem asks us to identify, from a list of divisors, the integer that has the maximum divisibility score with respect to a given array of numbers. The divisibility score of a divisor is defined as the count of elements in nums that are divisible by that divisor.

leetcodeeasyarray

LeetCode Problem 2644

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

The problem asks us to identify, from a list of divisors, the integer that has the maximum divisibility score with respect to a given array of numbers. The divisibility score of a divisor is defined as the count of elements in nums that are divisible by that divisor. In simpler terms, for each divisor, we count how many numbers in the array nums can be divided evenly by it. Among all divisors, we want the one with the highest count, and if there is a tie, we return the smallest divisor.

The input consists of two integer arrays: nums and divisors. Each integer can be up to 10^9, but the lengths of the arrays are capped at 1000. The constraints are small enough that a brute-force solution of checking each number in nums against every divisor is feasible, though an optimized solution is straightforward.

Key edge cases include divisors with no matches in nums, multiple divisors with the same maximum score, and scenarios where all numbers in nums are divisible by one divisor. The problem guarantees non-empty arrays and positive integers, so we do not need to handle zeros or empty inputs.

Approaches

The brute-force approach iterates through each divisor and checks every number in nums to see if it is divisible. This is correct because it directly computes the divisibility score for every divisor. However, this requires O(n * m) operations, where n is the length of nums and m is the length of divisors. Given the constraints (both up to 1000), this results in at most 1,000,000 checks, which is acceptable for this problem.

The optimal approach is essentially the same as brute force because the problem size is small. There is no need for sophisticated techniques like sieving or hashing, as a direct double iteration suffices. The key is to maintain both the maximum score and the corresponding smallest divisor while iterating, ensuring ties are handled correctly.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(1) Check each divisor against all numbers in nums, track maximum score
Optimal O(n * m) O(1) Same as brute force, but with tie-breaking logic for smallest divisor

Algorithm Walkthrough

  1. Initialize two variables: max_score to zero to track the highest divisibility score found so far, and best_divisor to a large number to ensure the first comparison updates it.
  2. Iterate over each divisor in divisors.
  3. For the current divisor, initialize a counter to zero.
  4. Iterate over each number in nums and increment the counter if the number is divisible by the current divisor.
  5. After counting, compare the counter with max_score. If it is higher, update max_score and set best_divisor to the current divisor. If it is equal, update best_divisor only if the current divisor is smaller than the existing best_divisor.
  6. Continue this process until all divisors are evaluated.
  7. Return best_divisor as the result.

Why it works: At every step, we maintain the maximum divisibility score and the smallest divisor achieving it. This invariant ensures that after processing all divisors, best_divisor contains the correct value according to the problem's requirements.

Python Solution

from typing import List

class Solution:
    def maxDivScore(self, nums: List[int], divisors: List[int]) -> int:
        max_score = 0
        best_divisor = float('inf')
        
        for divisor in divisors:
            count = 0
            for num in nums:
                if num % divisor == 0:
                    count += 1
            
            if count > max_score or (count == max_score and divisor < best_divisor):
                max_score = count
                best_divisor = divisor
        
        return best_divisor

Implementation walkthrough: We start by initializing max_score and best_divisor. For each divisor, we count how many numbers it divides evenly. If this count beats our current maximum, we update both max_score and best_divisor. If there is a tie, we only update best_divisor if the new divisor is smaller, ensuring the correct tie-breaking behavior.

Go Solution

func maxDivScore(nums []int, divisors []int) int {
    maxScore := 0
    bestDivisor := int(1e9 + 1) // initialize larger than any possible divisor
    
    for _, divisor := range divisors {
        count := 0
        for _, num := range nums {
            if num % divisor == 0 {
                count++
            }
        }
        if count > maxScore || (count == maxScore && divisor < bestDivisor) {
            maxScore = count
            bestDivisor = divisor
        }
    }
    return bestDivisor
}

Go-specific notes: We use 1e9 + 1 to initialize bestDivisor to ensure the first divisor updates it. Go does not require explicit type hints for slices, and we handle all numbers as int since constraints are within safe ranges.

Worked Examples

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

Divisor Count Max? Best Divisor
5 2 Yes 5
3 2 Tie 3 (update to smaller: 3)
7 0 No 3
2 2 Tie 2 (update to smaller: 2)

Result: 2

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

Divisor Count Max? Best Divisor
5 0 No 0
2 1 Yes 2
3 3 Yes 3

Result: 3

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

Divisor Count Max? Best Divisor
10 2 Yes 10
16 0 No 10
20 1 No 10

Result: 10

Complexity Analysis

Measure Complexity Explanation
Time O(n * m) Each divisor is checked against every number in nums, resulting in n*m operations
Space O(1) Only a few integer variables are used; no additional data structures needed

Given n, m ≤ 1000, the maximum of 1,000,000 operations is efficiently handled.

Test Cases

# Provided examples
assert Solution().maxDivScore([2,9,15,50], [5,3,7,2]) == 2  # multiple ties, smallest divisor returned
assert Solution().maxDivScore([4,7,9,3,9], [5,2,3]) == 3    # clear winner
assert Solution().maxDivScore([20,14,21,10], [10,16,20]) == 10 # max divisor is first

# Edge cases
assert Solution().maxDivScore([1,1,1,1], [1]) == 1           # all nums divisible by 1
assert Solution().maxDivScore([1,2,3,4,5], [10,20,30]) == 10 # no divisors match, return first smallest
assert Solution().maxDivScore([1000000000], [1,2,1000000000]) == 1 # large numbers
Test Why
[2,9,15,50], [5,3,7,2] Tests tie-breaking among divisors
[4,7,9,3,9], [5,2,3] Tests clear winner
[20,14,21,10], [10,16,20] Tests selection when first divisor has max score
[1,1,1,1], [1] Tests all numbers divisible by divisor
[1,2,3,4,5], [10,20,30] Tests no divisors match
[1000000000], [1,2,1000000000] Tests large numbers

Edge Cases

One important edge case is when all divisors have a score of zero, meaning no number in nums is divisible by any divisor. The implementation correctly returns the smallest divisor due to the tie-breaking logic, which is triggered when counts are equal (including zero).

Another edge case is when multiple divisors share the maximum score. Without careful handling, a naive implementation might return the last encountered divisor. By explicitly checking for divisor < best_divisor when scores tie, we ensure the smallest one is chosen.

A third edge case involves very large numbers, approaching 10^9. Python handles large integers natively, so there is no risk of overflow. In Go, the solution uses int, which can safely hold