algoadvance

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 is more than one integer with the maximum score, return the minimum one.

Example 1:

Input: nums = [4,7,9,3,9], divisors = [5,2,3]
Output: 3
Explanation: The divisibility score for every element in divisors is:
The divisibility score for divisors[0] is 0 since no number in nums is divisible by 5.
The divisibility score for divisors[1] is 1 since only nums[0] is divisible by 2.
The divisibility score for divisors[2] is 3 since nums[2], nums[3], and nums[4] are divisible by 3.
Since divisors[2] has the maximum divisibility score, we return 3.

Example 2:

Input: nums = [20,14,21,10], divisors = [5,7,5]
Output: 5
Explanation: The divisibility score for every element in divisors is:
The divisibility score for divisors[0] is 2 since nums[0] and nums[3] are divisible by 5.
The divisibility score for divisors[1] is 2 since nums[1] and nums[2] are divisible by 7.
The divisibility score for divisors[2] is 2 since nums[0] and nums[3] are divisible by 5.
Since divisors[0], divisors[1], and divisors[2] all have the same maximum divisibility score, we return the minimum one which is 5.

Constraints:

• 1 <= nums.length, divisors.length <= 1000
• 1 <= nums[i], divisors[i] <= 1000

Clarifying Questions

Before proceeding, let’s clarify some questions:

1. Are there any constraints on the size of the arrays?
   • Already specified in the problem: (1 \leq \text{nums.length, divisors.length} \leq 1000).
2. What should be returned if both arrays are empty?
   • As per the problem constraint, array lengths are always at least 1.

Strategy

1. Initialize a dictionary to keep count of divisibility scores for each divisor.
2. For each divisor, iterate through the nums array and check divisibility.
3. Track the maximum score and the corresponding divisor(s).
4. If there are multiple divisors with the same maximum score, return the smallest one.
5. Return the divisor with the highest score.

Code

Here’s the Python code to solve this problem:

def maxDivScore(nums, divisors):
    max_score = 0
    optimal_divisor = float('inf')

    for divisor in divisors:
        score = sum(1 for num in nums if num % divisor == 0)
        
        if score > max_score or (score == max_score and divisor < optimal_divisor):
            max_score = score
            optimal_divisor = divisor
    
    return optimal_divisor

# Example usage:
nums1 = [4, 7, 9, 3, 9]
divisors1 = [5, 2, 3]
print(maxDivScore(nums1, divisors1))  # Output: 3

nums2 = [20, 14, 21, 10]
divisors2 = [5, 7, 5]
print(maxDivScore(nums2, divisors2))  # Output: 5

Time Complexity

Let’s analyze the time complexity of our algorithm:

• Iterating through each divisor takes (O(d)) time where (d) is the length of the divisors array.
• For each divisor, we iterate through the nums array to count divisibility, which takes (O(n)) time where (n) is the length of the nums array.

Thus, the overall time complexity is (O(n \times d)), which is efficient given the constraints.

Summary

• We defined our approach to count the divisibility scores for each divisor.
• We ensured to handle the case of ties by selecting the smallest divisor.
• We analyzed and ensured that our solution is efficient for the given constraints.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?