2644. Find the Maximum Divisibility Score
SourceWeekly Contest 341 Q2DifficultyEasyRating1257
Description
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
Solutions
Solution 1: Enumeration
Thinking
The score is how many \(\textit{nums}\) are divisible by a candidate; ties take the smaller divisor. Both arrays have length \(\le 1000\), so each divisor can scan \(\textit{nums}\).
Keep the best count and its divisor; on a tie, replace it with the smaller \(\textit{div}\).
We can enumerate each element \(\textit{div}\) in \(\textit{divisors}\), and calculate how many elements in \(\textit{nums}\) can be divided by \(\textit{div}\), denoted as \(\textit{cnt}\).
- If \(\textit{cnt}\) is greater than the current maximum divisibility score \(mx\), then update \(mx = \textit{cnt}\), and update \(\textit{ans} = \textit{div}\).
- If \(\textit{cnt}\) equals \(mx\) and \(\textit{div}\) is less than \(\textit{ans}\), then update \(\textit{ans} = \textit{div}\).
Finally, return \(\textit{ans}\).
The time complexity is \(O(mn)\), and the space complexity is \(O(1)\), where \(m\) and \(n\) are the lengths of \(\textit{nums}\) and \(\textit{divisors}\) respectively.
1 2 3 4 5 6 7 8 9 10 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | |