# Find the Maximum Divisibility Score
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-maximum-divisibility-score)
Canonical: https://scaleengineer.com/dsa/problems/find-the-maximum-divisibility-score
**Data structures:** Array
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
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 <= 1000`
* `1 <= nums[i], divisors[i] <= 109`

# Approaches
## Brute-Force Iteration
This is the most direct approach. We iterate through each element in the `divisors` array. For each divisor, we then iterate through the `nums` array to calculate its divisibility score. We maintain a variable for the maximum score seen so far and the corresponding divisor, updating them as we find a better candidate according to the problem's rules.
**Time:** O(m * n), where `m` is the number of divisors and `n` is the number of elements in `nums`. This is because for each of the `m` divisors, we iterate through all `n` numbers. · **Space:** O(1), as we only use a constant amount of extra space for variables like `maxScore`, `currentScore`, and `resultDivisor`.
**Pros:** Very simple to understand and implement.; Requires no extra space.; Sufficiently fast for the given constraints.
**Cons:** Performs redundant calculations if the `divisors` array contains duplicate values, as it will re-calculate the score for each duplicate.; The logic for tie-breaking adds a small amount of complexity compared to a pre-sorted approach.
### Explanation
The algorithm proceeds as follows:
1.  Initialize `maxScore` to -1 and `resultDivisor` to a very large value (like `Integer.MAX_VALUE`) to ensure any valid divisor will be smaller.
2.  Loop through each `divisor` in the `divisors` array.
3.  For each `divisor`, calculate its score by initializing a `currentScore` to 0 and then iterating through `nums`, incrementing the score for each number divisible by the current `divisor`.
4.  After calculating the `currentScore`, compare it with `maxScore`.
    *   If `currentScore` is greater than `maxScore`, we've found a new best score. We update `maxScore` to `currentScore` and `resultDivisor` to the current `divisor`.
    *   If `currentScore` is equal to `maxScore`, the problem requires us to choose the smaller divisor. So, we update `resultDivisor` to be the minimum of its current value and the current `divisor`.
5.  After checking all divisors, `resultDivisor` will hold the final answer.

```java
class Solution {
    public int maxDivScore(int[] nums, int[] divisors) {
        int maxScore = -1;
        int resultDivisor = Integer.MAX_VALUE;

        for (int divisor : divisors) {
            int currentScore = 0;
            for (int num : nums) {
                if (num % divisor == 0) {
                    currentScore++;
                }
            }

            if (currentScore > maxScore) {
                maxScore = currentScore;
                resultDivisor = divisor;
            } else if (currentScore == maxScore) {
                resultDivisor = Math.min(resultDivisor, divisor);
            }
        }
        return resultDivisor;
    }
}
```
### Algorithm
*   Initialize `maxScore = -1` and `resultDivisor = Integer.MAX_VALUE`.
*   For each `d` in `divisors`:
    *   Initialize `currentScore = 0`.
    *   For each `n` in `nums`:
        *   If `n % d == 0`, increment `currentScore`.
    *   If `currentScore > maxScore`:
        *   Set `maxScore = currentScore`.
        *   Set `resultDivisor = d`.
    *   Else if `currentScore == maxScore`:
        *   Set `resultDivisor = min(resultDivisor, d)`.
*   Return `resultDivisor`.

## Optimized Iteration with Pre-sorting
This approach enhances the brute-force method by first sorting the `divisors` array. By processing divisors in ascending order, the logic for handling ties becomes much simpler. The first divisor we encounter for a given score will always be the smallest one, so we only need to update our result when we find a strictly greater score.
**Time:** O(m log m + m * n), where `m` is the length of `divisors` and `n` is the length of `nums`. The `m log m` term comes from sorting, and `m * n` comes from the nested loops. The `m * n` term dominates. · **Space:** O(log m) or O(m) depending on the implementation of the sorting algorithm used. This is the space required for sorting.
**Pros:** Simplifies the tie-breaking logic, leading to cleaner code.; Avoids redundant work by skipping duplicate divisors.; More efficient in practice if `divisors` has many duplicates.
**Cons:** The worst-case time complexity is asymptotically the same as the brute-force approach.; Incurs an initial cost of O(m log m) for sorting.
### Explanation
The algorithm is as follows:
1.  Sort the `divisors` array in ascending order. This step is key to simplifying the tie-breaking logic.
2.  Initialize `maxScore` to -1 and `resultDivisor` to a default value, like the first element of the sorted `divisors` array (`divisors[0]`). Since `divisors` is guaranteed to have at least one element, this is a safe default.
3.  Iterate through the sorted `divisors` array. To be more efficient, you can skip any divisor that is the same as the one preceding it, avoiding redundant calculations.
4.  For each unique `divisor`, calculate its `currentScore` by iterating through `nums`.
5.  Compare `currentScore` with `maxScore`. If `currentScore > maxScore`, update `maxScore` to `currentScore` and `resultDivisor` to the current `divisor`.
6.  Because the divisors are sorted, if `currentScore == maxScore`, we don't need to do anything. The `resultDivisor` we already have is smaller than or equal to the current divisor, so it remains the correct choice.
7.  After the loop, `resultDivisor` holds the answer.

```java
import java.util.Arrays;

class Solution {
    public int maxDivScore(int[] nums, int[] divisors) {
        Arrays.sort(divisors);
        
        int maxScore = -1;
        int resultDivisor = divisors[0]; 
        
        for (int i = 0; i < divisors.length; i++) {
            // Skip duplicate divisors to avoid re-computation
            if (i > 0 && divisors[i] == divisors[i-1]) {
                continue;
            }
            
            int divisor = divisors[i];
            int currentScore = 0;
            for (int num : nums) {
                if (num % divisor == 0) {
                    currentScore++;
                }
            }

            if (currentScore > maxScore) {
                maxScore = currentScore;
                resultDivisor = divisor;
            }
        }
        return resultDivisor;
    }
}
```
### Algorithm
*   Sort the `divisors` array in ascending order.
*   Initialize `maxScore = -1`.
*   Initialize `resultDivisor = divisors[0]`.
*   For each `d` in `divisors`:
    *   (Optional) If `d` is the same as the previous divisor, continue to the next iteration.
    *   Initialize `currentScore = 0`.
    *   For each `n` in `nums`:
        *   If `n % d == 0`, increment `currentScore`.
    *   If `currentScore > maxScore`:
        *   Set `maxScore = currentScore`.
        *   Set `resultDivisor = d`.
*   Return `resultDivisor`.

# Solutions
### Java

```java
class Solution { public int maxDivScore ( int [] nums , int [] divisors ) { int ans = divisors [ 0 ]; int mx = 0 ; for ( int div : divisors ) { int cnt = 0 ; for ( int x : nums ) { if ( x % div == 0 ) { ++ cnt ; } } if ( mx < cnt ) { mx = cnt ; ans = div ; } else if ( mx == cnt ) { ans = Math . min ( ans , div ); } } return ans ; } }
```

### Python

```python
class Solution : def maxDivScore ( self , nums : List [ int ], divisors : List [ int ]) -> int : ans , mx = divisors [ 0 ], 0 for div in divisors : cnt = sum ( x % div == 0 for x in nums ) if mx < cnt : mx , ans = cnt , div elif mx == cnt and ans > div : ans = div return ans
```

### CPP

```cpp
class Solution { public: int maxDivScore ( vector < int >& nums , vector < int >& divisors ) { int ans = divisors [ 0 ]; int mx = 0 ; for ( int div : divisors ) { int cnt = 0 ; for ( int x : nums ) { cnt += x % div == 0 ; } if ( mx < cnt ) { mx = cnt ; ans = div ; } else if ( mx == cnt ) { ans = min ( ans , div ); } } return ans ; } };
```