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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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] <= 10^9

Solution

Method 1 – Brute Force Count

Intuition

For each divisor, count how many numbers in nums are divisible by it. Track the divisor with the highest count, and in case of a tie, choose the smallest divisor.

Approach

  1. For each divisor in divisors, count the number of elements in nums divisible by it.
  2. Track the maximum score and the smallest divisor with that score.
  3. Return the smallest divisor with the maximum score.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int maxDivScore(vector<int>& nums, vector<int>& divs) {
        int mx = -1, ans = 0;
        for(int d : divs) {
            int cnt = 0;
            for(int x : nums) if(x%d==0) ++cnt;
            if(cnt > mx || (cnt == mx && d < ans)) {
                mx = cnt; ans = d;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func maxDivScore(nums []int, divs []int) int {
    mx, ans := -1, 0
    for _, d := range divs {
        cnt := 0
        for _, x := range nums {
            if x%d == 0 { cnt++ }
        }
        if cnt > mx || (cnt == mx && d < ans) {
            mx, ans = cnt, d
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int maxDivScore(int[] nums, int[] divs) {
        int mx = -1, ans = 0;
        for(int d : divs) {
            int cnt = 0;
            for(int x : nums) if(x%d==0) ++cnt;
            if(cnt > mx || (cnt == mx && d < ans)) {
                mx = cnt; ans = d;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun maxDivScore(nums: IntArray, divs: IntArray): Int {
        var mx = -1; var ans = 0
        for (d in divs) {
            var cnt = 0
            for (x in nums) if (x % d == 0) cnt++
            if (cnt > mx || (cnt == mx && d < ans)) {
                mx = cnt; ans = d
            }
        }
        return ans
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def maxDivScore(self, nums: list[int], divs: list[int]) -> int:
        mx, ans = -1, 0
        for d in divs:
            cnt = sum(x%d==0 for x in nums)
            if cnt > mx or (cnt == mx and (ans == 0 or d < ans)):
                mx, ans = cnt, d
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn max_div_score(nums: Vec<i32>, divs: Vec<i32>) -> i32 {
        let mut mx = -1;
        let mut ans = 0;
        for &d in &divs {
            let cnt = nums.iter().filter(|&&x| x%d==0).count() as i32;
            if cnt > mx || (cnt == mx && d < ans) {
                mx = cnt; ans = d;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    maxDivScore(nums: number[], divs: number[]): number {
        let mx = -1, ans = 0;
        for(const d of divs) {
            let cnt = 0;
            for(const x of nums) if(x%d===0) ++cnt;
            if(cnt > mx || (cnt === mx && d < ans)) {
                mx = cnt; ans = d;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(mn), where m is the number of divisors and n is the number of nums.
  • 🧺 Space complexity: O(1), only a few variables are used.