Find the Maximum Divisibility Score

Problem 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.

Key Insights

• The problem requires calculating how many numbers in nums are divisible by each divisor in divisors.
• It is necessary to keep track of both the maximum score and the corresponding divisor.
• If multiple divisors have the same score, the smallest divisor should be returned.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of nums and m is the length of divisors (since we may need to check each number in nums for each divisor). Space Complexity: O(1), as we are using a fixed amount of space regardless of the input size.

Solution

To solve the problem, we will iterate through each divisor in the divisors array and count how many numbers in the nums array are divisible by that divisor. We will maintain a variable to track the maximum score and the smallest divisor that achieves that score.

• Use a loop to go through each divisor.
• For each divisor, use a nested loop to count how many elements in nums are divisible by the current divisor.
• Compare the current score with the maximum score; if it's higher, update the maximum score and the corresponding divisor. If it's equal, choose the smaller divisor.

Code Solutions