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 <= 10001 <= nums[i], divisors[i] <= 109Problem 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.
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.
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.
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.
Time Complexity: O(n * m), potentially approaching O(n) with early exits.
Space Complexity: O(1).
We can enumerate each element div in divisors, and calculate how many elements in nums can be divided by div, denoted as cnt.
cnt is greater than the current maximum divisibility score mx, then update mx = cnt, and update ans = div.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).
| Approach | Complexity |
|---|---|
| Naive Iterative Approach | Time Complexity: |
| Optimized Counting with Early Exit | Time Complexity: |
| Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Iterative Approach | O(n * m) | O(1) | General case. Simple implementation when input sizes are moderate. |
| Optimized Counting with Early Exit | O(n * m) worst case | O(1) | When many divisors quickly become worse candidates and loops can terminate early. |
Leetcode 2644. Find the Maximum Divisibility Score | Contest 341 | Leetcode weekly contest Solution • OffCampus Phodenge | Aman Chowdhury • 344 views views
Watch 9 more video solutions →Practice Find the Maximum Divisibility Score with our built-in code editor and test cases.
Practice on FleetCode