Watch 10 video solutions for Find the Maximum Divisibility Score, a easy level problem involving Array. This walkthrough by OffCampus Phodenge | Aman Chowdhury has 344 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |