Find the Maximum Divisibility Score
EasyPrompt
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] <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
This is the most direct approach. We iterate through each element in the divisors array. For each divisor, we then iterate through the nums array to calculate its divisibility score. We maintain a variable for the maximum score seen so far and the corresponding divisor, updating them as we find a better candidate according to the problem's rules.
Algorithm
- Initialize
maxScore = -1andresultDivisor = Integer.MAX_VALUE. - For each
dindivisors:- Initialize
currentScore = 0. - For each
ninnums:- If
n % d == 0, incrementcurrentScore.
- If
- If
currentScore > maxScore:- Set
maxScore = currentScore. - Set
resultDivisor = d.
- Set
- Else if
currentScore == maxScore:- Set
resultDivisor = min(resultDivisor, d).
- Set
- Initialize
- Return
resultDivisor.
Walkthrough
The algorithm proceeds as follows:
- Initialize
maxScoreto -1 andresultDivisorto a very large value (likeInteger.MAX_VALUE) to ensure any valid divisor will be smaller. - Loop through each
divisorin thedivisorsarray. - For each
divisor, calculate its score by initializing acurrentScoreto 0 and then iterating throughnums, incrementing the score for each number divisible by the currentdivisor. - After calculating the
currentScore, compare it withmaxScore.- If
currentScoreis greater thanmaxScore, we've found a new best score. We updatemaxScoretocurrentScoreandresultDivisorto the currentdivisor. - If
currentScoreis equal tomaxScore, the problem requires us to choose the smaller divisor. So, we updateresultDivisorto be the minimum of its current value and the currentdivisor.
- If
- After checking all divisors,
resultDivisorwill hold the final answer.
class Solution { public int maxDivScore(int[] nums, int[] divisors) { int maxScore = -1; int resultDivisor = Integer.MAX_VALUE; for (int divisor : divisors) { int currentScore = 0; for (int num : nums) { if (num % divisor == 0) { currentScore++; } } if (currentScore > maxScore) { maxScore = currentScore; resultDivisor = divisor; } else if (currentScore == maxScore) { resultDivisor = Math.min(resultDivisor, divisor); } } return resultDivisor; }}Complexity
Time
O(m * n), where `m` is the number of divisors and `n` is the number of elements in `nums`. This is because for each of the `m` divisors, we iterate through all `n` numbers.
Space
O(1), as we only use a constant amount of extra space for variables like `maxScore`, `currentScore`, and `resultDivisor`.
Trade-offs
Pros
Very simple to understand and implement.
Requires no extra space.
Sufficiently fast for the given constraints.
Cons
Performs redundant calculations if the
divisorsarray contains duplicate values, as it will re-calculate the score for each duplicate.The logic for tie-breaking adds a small amount of complexity compared to a pre-sorted approach.
This approach enhances the brute-force method by first sorting the divisors array. By processing divisors in ascending order, the logic for handling ties becomes much simpler. The first divisor we encounter for a given score will always be the smallest one, so we only need to update our result when we find a strictly greater score.
Algorithm
- Sort the
divisorsarray in ascending order. - Initialize
maxScore = -1. - Initialize
resultDivisor = divisors[0]. - For each
dindivisors:- (Optional) If
dis the same as the previous divisor, continue to the next iteration. - Initialize
currentScore = 0. - For each
ninnums:- If
n % d == 0, incrementcurrentScore.
- If
- If
currentScore > maxScore:- Set
maxScore = currentScore. - Set
resultDivisor = d.
- Set
- (Optional) If
- Return
resultDivisor.
Walkthrough
The algorithm is as follows:
- Sort the
divisorsarray in ascending order. This step is key to simplifying the tie-breaking logic. - Initialize
maxScoreto -1 andresultDivisorto a default value, like the first element of the sorteddivisorsarray (divisors[0]). Sincedivisorsis guaranteed to have at least one element, this is a safe default. - Iterate through the sorted
divisorsarray. To be more efficient, you can skip any divisor that is the same as the one preceding it, avoiding redundant calculations. - For each unique
divisor, calculate itscurrentScoreby iterating throughnums. - Compare
currentScorewithmaxScore. IfcurrentScore > maxScore, updatemaxScoretocurrentScoreandresultDivisorto the currentdivisor. - Because the divisors are sorted, if
currentScore == maxScore, we don't need to do anything. TheresultDivisorwe already have is smaller than or equal to the current divisor, so it remains the correct choice. - After the loop,
resultDivisorholds the answer.
import java.util.Arrays; class Solution { public int maxDivScore(int[] nums, int[] divisors) { Arrays.sort(divisors); int maxScore = -1; int resultDivisor = divisors[0]; for (int i = 0; i < divisors.length; i++) { // Skip duplicate divisors to avoid re-computation if (i > 0 && divisors[i] == divisors[i-1]) { continue; } int divisor = divisors[i]; int currentScore = 0; for (int num : nums) { if (num % divisor == 0) { currentScore++; } } if (currentScore > maxScore) { maxScore = currentScore; resultDivisor = divisor; } } return resultDivisor; }}Complexity
Time
O(m log m + m * n), where `m` is the length of `divisors` and `n` is the length of `nums`. The `m log m` term comes from sorting, and `m * n` comes from the nested loops. The `m * n` term dominates.
Space
O(log m) or O(m) depending on the implementation of the sorting algorithm used. This is the space required for sorting.
Trade-offs
Pros
Simplifies the tie-breaking logic, leading to cleaner code.
Avoids redundant work by skipping duplicate divisors.
More efficient in practice if
divisorshas many duplicates.
Cons
The worst-case time complexity is asymptotically the same as the brute-force approach.
Incurs an initial cost of O(m log m) for sorting.
Solutions
Solution
class Solution { public int maxDivScore ( int [] nums , int [] divisors ) { int ans = divisors [ 0 ]; int mx = 0 ; for ( int div : divisors ) { int cnt = 0 ; for ( int x : nums ) { if ( x % div == 0 ) { ++ cnt ; } } if ( mx < cnt ) { mx = cnt ; ans = div ; } else if ( mx == cnt ) { ans = Math . min ( ans , div ); } } return ans ; } }class Solution : def maxDivScore ( self , nums : List [ int ], divisors : List [ int ]) -> int : ans , mx = divisors [ 0 ], 0 for div in divisors : cnt = sum ( x % div == 0 for x in nums ) if mx < cnt : mx , ans = cnt , div elif mx == cnt and ans > div : ans = div return ansclass Solution { public: int maxDivScore ( vector < int >& nums , vector < int >& divisors ) { int ans = divisors [ 0 ]; int mx = 0 ; for ( int div : divisors ) { int cnt = 0 ; for ( int x : nums ) { cnt += x % div == 0 ; } if ( mx < cnt ) { mx = cnt ; ans = div ; } else if ( mx == cnt ) { ans = min ( ans , div ); } } return ans ; } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.