Skip to main content
Talentd

Find the Maximum Divisibility Score - Solution & Explanation

EasyArray18 min readAsked at: De Shaw
Practice this problem

Problem Statement

You are given two integer arrays nums and divisors.

The divisibility score of divisors[i] is the number of indices j such that nums[j] is divisible by divisors[i].

Return the integer divisors[i] with the maximum divisibility score. If multiple integers have the maximum score, return the smallest one.

 

Example 1:

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

Output: 2

Explanation:

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

Explanation:

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

Explanation:

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

Approach Overview

Problem Overview: You are given an integer array nums and another array divisors. For every divisor, count how many numbers in nums are divisible by it. The divisor with the highest count (divisibility score) is returned. If multiple divisors produce the same score, return the smallest divisor.

Approach 1: Naive Iterative Approach (O(n * m) time, O(1) space)

Loop through every value in divisors and compute its divisibility score by iterating through the nums array. For each pair, check num % divisor == 0. Maintain two variables: the best score seen so far and the corresponding smallest divisor that produced it. If a new divisor produces a larger score, update both values. If the score ties with the current maximum, keep the smaller divisor.

This method relies on straightforward iteration over arrays. The logic is simple and easy to implement in any language. Because every divisor checks every element in nums, the total work is proportional to len(nums) * len(divisors). Space usage stays constant since only counters and the result variable are stored.

Approach 2: Optimized Counting with Early Exit (O(n * m) worst-case time, O(1) space)

The counting logic stays the same, but the loop can terminate early when the current divisor can no longer beat the best score. While scanning nums, track the current score. If the remaining elements plus the current score cannot exceed the best score already found, break the loop early. This avoids unnecessary modulo checks for clearly worse candidates.

This optimization works well when the best divisor appears early or when divisibility is sparse. The algorithm still operates on array traversal and simple math operations such as modulo. Worst‑case complexity remains O(n * m), but practical runtime improves because many divisor checks terminate early.

Recommended for interviews: Start with the naive iterative approach. It clearly demonstrates the divisibility scoring logic and tie‑breaking rule. Then mention the early‑exit optimization to reduce unnecessary checks. Interviewers expect the straightforward O(n * m) scan because the constraints are small and the problem primarily tests careful iteration and condition handling.

Approach 1: Naive Iterative Approach

This approach involves iterating through each element in the divisors list and calculating the divisibility score by counting how many elements in the nums list are perfectly divisible by the current divisor. We maintain a variable to track the maximum score and update it as necessary. In the case of a tie, we select the smallest divisor.

We define a function findMaxDivisor that takes the arrays nums and divisors, iterating through each divisor to count the divisibility score. We then compare scores, updating the best divisor when a higher score is found or when scores are the same and the current divisor is smaller. The main function demonstrates the function with example input.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m), where n is the length of nums and m is the length of divisors.
Space Complexity: O(1), as no additional space is used proportional to the input size.

Try this approach in the editor →

Approach 2: Optimized Counting with Early Exit

This approach enhances efficiency by seeking an early exit on obvious winners during processing. Instead of evaluating every divisor in a linear pass, we update our search to check if potential divisors far outweigh the best without scanning every nums element against it.

We optimize the iterative process by introducing a break statement inside the loop as soon as a dominantly higher score surfaces that no other potential divisor can outmatch. While still simplistic, this approach curtails some unnecessary checks.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m), potentially approaching O(n) with early exits.
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Enumeration

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

  • If cnt is greater than the current maximum divisibility score mx, then update mx = cnt, and update ans = div.
  • If cnt equals mx and div is less than ans, then update ans = div.

Finally, return ans.

The time complexity is O(m times n), where m and n are the lengths of nums and divisors respectively. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Naive Iterative Approach

Time Complexity: O(n * m), where n is the length of nums and m is the length of divisors.
Space Complexity: O(1), as no additional space is used proportional to the input size.

Optimized Counting with Early Exit

Time Complexity: O(n * m), potentially approaching O(n) with early exits.
Space Complexity: O(1).

Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive Iterative ApproachO(n * m)O(1)General case. Simple implementation when input sizes are moderate.
Optimized Counting with Early ExitO(n * m) worst caseO(1)When many divisors quickly become worse candidates and loops can terminate early.

Video Solution

Leetcode 2644. Find the Maximum Divisibility Score | Contest 341 | Leetcode weekly contest Solution • OffCampus Phodenge | Aman Chowdhury • 345 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Maximum Divisibility Score easy or hard?
Find the Maximum Divisibility Score is classified as an Easy problem. The core logic involves basic array traversal and counting divisible elements. The only tricky part is handling the tie condition by selecting the smallest divisor.
Find the Maximum Divisibility Score Python/Java solution
The implementation in Python or Java loops through each divisor and counts how many elements in nums satisfy num % divisor == 0. Maintain variables for the best score and the smallest divisor producing that score. This results in O(n * m) time and constant extra space.
How to solve Find the Maximum Divisibility Score in O(n)?
A strict O(n) solution is generally not possible because every divisor must be evaluated to compute its score. The optimal practical approach scans nums for each divisor, resulting in O(n * m) time. Minor optimizations such as early exit during counting can reduce unnecessary checks.
What is the best approach for Find the Maximum Divisibility Score?
The most practical approach iterates through each divisor and counts how many numbers in the nums array are divisible by it. Track the maximum score and return the smallest divisor when scores tie. This runs in O(n * m) time where n is the length of nums and m is the number of divisors, with O(1) extra space.
Is Find the Maximum Divisibility Score asked at Google/Amazon/Meta?
Problems involving divisibility checks and array iteration appear frequently in coding interviews at large tech companies. While this exact problem may not always appear, similar tasks testing array traversal, modulo operations, and tie‑breaking logic are common in interviews at companies like Amazon and Google.
What data structure is used in Find the Maximum Divisibility Score?
The problem primarily uses arrays for both nums and divisors. The algorithm relies on sequential traversal and simple arithmetic operations such as modulo. No advanced data structures are required.
What is the time complexity of Find the Maximum Divisibility Score?
The typical solution runs in O(n * m) time because each divisor checks divisibility against every element in nums. Space complexity is O(1) since only counters and result variables are used. Early termination optimizations can reduce runtime in practice but do not change the worst‑case complexity.

Ready to solve this problem?

Practice Find the Maximum Divisibility Score with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Prefix Divisible By 5