2644. Find the Maximum Divisibility Score

Problem Description

The problem provides us with two arrays: nums (containing integers) and divisors (containing possible divisors). We are tasked with finding the integer from divisors which has the highest divisibility score, where the divisibility score of an element in divisors is the count of elements in nums that it can divide evenly (without leaving a remainder). In case more than one divisor has the same highest score, we need to return the smallest among them.

To put it simply, we want to answer the question: "Which number in divisors divides the most numbers in nums with no remainder?" and if there's a tie, we select the smallest number.

Intuition

This problem is suited for a brute force approach that checks each number in divisors against every number in nums to calculate its divisibility score.

• We begin by setting a variable mx to 0, to keep track of the maximum score found so far, and another variable ans to keep the divisor with the maximum score. We initialize ans with the first element of divisors since we need to return an element from divisors in case all scores are zero.

• We iterate over each divisor in divisors. For each divisor, we count how many numbers in nums are divisible by it. This is done using a summation with a conditional check, where we use the modulo operator % to test if the remainder is zero (meaning divisibility).

• If the current divisor's score is greater than the maximum score we've seen (mx), we update mx with this new score and also update ans with the current divisor.

• If the current divisor's score is equal to the maximum score but less than the current ans, we update ans to this divisor since it is smaller and we want the smallest divisor in case of a tie.

By the end of the iteration, ans will hold the divisor with the highest divisibility score, and in the case of a tie, the smallest one amongst them. This algorithm guarantees that we look at each possibility, and eventually, the correct answer is identified and returned.

Solution Approach

The solution provided in the reference code implements the brute force approach described in the intuition section. Here is a detailed breakdown of the approach:

• We have a for loop that goes through each element div in the divisors array.
• Inside the loop, we have a key expression sum(x % div == 0 for x in nums). This expression counts the number of elements in nums that are divisible by div (the x % div == 0 part checks if x is divisible by div without a remainder).
  • This is a generator comprehension within the sum function that goes over each element x in nums and yields 1 if x is divisible by div, and 0 otherwise. The sum function then adds up these 0s and 1s to get the total count.
• The cnt variable is used to hold this count, which represents the divisibility score of the current divisor div.
• We compare cnt against mx to determine if we have found a higher divisibility score:
  • If cnt is greater than mx, we have indeed found a new divisor with a higher score. We assign cnt to mx, and div to ans.
  • If cnt is equal to mx but div is smaller than the current ans, then we update ans with div. This ensures that among divisors with the same highest score, we will return the smallest divisor.
• No additional data structures are required, making this approach efficient in terms of space complexity. The time complexity can be considered as O(n * m), where 'n' is the length of the nums array and 'm' is the length of the divisors array, since each divisor is checked against all nums.

The algorithm employs a simple comparison-based technique, and its strength lies in its straightforwardness and direct mapping to the problem statement without any need for optimization tricks or complicated data structures. This is highly suitable for scenarios where the array sizes are manageable and high efficiency is not a critical requirement.

Example Walkthrough

Let's consider two small arrays to illustrate the solution approach:

• nums = [4, 8, 12]
• divisors = [2, 3, 4]

Now, we want to figure out which number in divisors can divide the most numbers in nums without leaving a remainder, and if there's a tie, we choose the smallest number.

1. We start with an initial maximum score mx set to 0 and the current answer ans set to the first element in divisors, which is 2.

2. We then iterate through each number in divisors to calculate its divisibility score:

   • When div = 2:
     • 4 % 2 == 0 (true, score is 1)
     • 8 % 2 == 0 (true, score is 2)
     • 12 % 2 == 0 (true, score is 3)
     • Total score for 2 is 3. mx is updated to 3, ans is updated to 2.
   • When div = 3:
     • 4 % 3 != 0 (false, score remains 0)
     • 8 % 3 != 0 (false, score remains 0)
     • 12 % 3 == 0 (true, score is 1)
     • Total score for 3 is 1, which is less than mx(3). We don't update mx or ans.
   • When div = 4:
     • 4 % 4 == 0 (true, score is 1)
     • 8 % 4 == 0 (true, score is 2)
     • 12 % 4 == 0 (true, score is 3)
     • Total score for 4 is also 3, equal to mx. However, since ans is smaller (2 < 4), we do not update ans.

3. After the iteration, the highest score is 3 with ans being 2. Since there's a tie between 2 and 4, we take the smaller number which is 2.

Thus, the final answer is 2, because it can divide all three numbers in nums with no remainder and is the smallest among the divisors with the highest divisibility score.

Solution Implementation

Time and Space Complexity

The given Python code defines the method maxDivScore which finds the divisor from the list divisors that maximizes the number of elements in nums that can be evenly divided by it. In case of ties, the smallest such divisor is returned.

Time Complexity:

The time complexity of the method can be determined by analyzing the for loop and the sum function within it. The for loop iterates once for each element in divisors. Inside the loop, the sum function iterates over each element in nums:

• Let n be the length of nums.
• Let d be the length of divisors.

For each divisor, we perform n modulus operations and n equality checks. Therefore, for all divisors, we perform this operation d times. The time complexity is O(n*d) because we have two nested loops: one iterating over divisors and the other over nums.

Space Complexity:

The space complexity is determined by the extra space used by the function beyond the input lists. In this case, the only extra space used are a few variables (ans, mx, div, and cnt) that remain constant regardless of input size. Hence, the space complexity is O(1) as there are no data structures used that scale with the size of the input.

Learn more about how to find time and space complexity quickly using problem constraints.