2644. Find the Maximum Divisibility Score#
You are given two 0-indexed 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 there are multiple integers with the maximum score, return the smallest one.
Example 1:
Input: nums = [4,7,9,3,9], divisors = [5,2,3]
Output: 3
Explanation: The divisibility score of each element in divisors is:
- The divisibility score of divisors[0] is 0 because there are no numbers in nums that are divisible by 5.
- The divisibility score of divisors[1] is 1 because nums[0] is divisible by 2.
- The divisibility score of divisors[2] is 3 because nums[2], nums[3], and nums[4] are all divisible by 3.
Therefore, we return divisors[2] since it has the maximum divisibility score.
Example 2:
Input: nums = [20,14,21,10], divisors = [5,7,5]
Output: 5
Explanation: The divisibility score of each element in divisors is:
- The divisibility score of divisors[0] is 2 because nums[0] and nums[3] are both divisible by 5.
- The divisibility score of divisors[1] is 2 because nums[1] and nums[2] are both divisible by 7.
- The divisibility score of divisors[2] is 2 because nums[0] and nums[3] are both divisible by 5.
Since the divisibility scores of divisors[0], divisors[1], and divisors[2] are all maximum, we return the smallest one, which is divisors[2].
Example 3:
Input: nums = [12], divisors = [10,16]
Output: 10
Explanation: The divisibility score of each element in divisors is:
- The divisibility score of divisors[0] is 0 because there are no numbers in nums that are divisible by 10.
- The divisibility score of divisors[1] is 0 because there are no numbers in nums that are divisible by 16.
Since the divisibility scores of divisors[0] and divisors[1] are both maximum, we return the smallest one, which is divisors[0].
Note:
Simulation#
class Solution {
public:
int maxDivScore(vector<int>& nums, vector<int>& divisors) {
int res = INT_MAX, cnt = 0;
for (const auto &divisor : divisors) {
int cur = 0;
for (const auto &num : nums) {
cur += (num % divisor == 0);
}
if (cur == cnt) {
res = min(res, divisor);
} else if (cur > cnt) {
res = divisor;
cnt = cur;
}
}
return res;
}
};