Welcome to Subscribe On Youtube

2644. Find the Maximum Divisibility Score

Description

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 of them.

 

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 of divisors[0] is 0 since no number in nums is divisible by 5.
The divisibility score of divisors[1] is 1 since 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.
Since divisors[2] has the maximum divisibility score, we return it.

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 of divisors[0] is 2 since nums[0] and nums[3] are divisible by 5.
The divisibility score of divisors[1] is 2 since nums[1] and nums[2] are divisible by 7.
The divisibility score of 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 maximum divisibility score, we return the minimum of them (i.e., divisors[2]).

Example 3:

Input: nums = [12], divisors = [10,16]
Output: 10
Explanation: The divisibility score for every element in divisors is:
The divisibility score of divisors[0] is 0 since no number in nums is divisible by 10.
The divisibility score of divisors[1] is 0 since no number in nums is divisible by 16.
Since divisors[0] and divisors[1] both have the maximum divisibility score, we return the minimum of them (i.e., divisors[0]).

 

Constraints:

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

Solutions

  • 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;
        }
    }
    
    
  • 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;
        }
    };
    
  • 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
    
    
  • func maxDivScore(nums []int, divisors []int) int {
    	ans, mx := divisors[0], 0
    	for _, div := range divisors {
    		cnt := 0
    		for _, x := range nums {
    			if x%div == 0 {
    				cnt++
    			}
    		}
    		if mx < cnt {
    			ans, mx = div, cnt
    		} else if mx == cnt && ans > div {
    			ans = div
    		}
    	}
    	return ans
    }
    
    
  • function maxDivScore(nums: number[], divisors: number[]): number {
        let ans: number = divisors[0];
        let mx: number = 0;
        for (const div of divisors) {
            const cnt = nums.reduce((a, b) => a + (b % div == 0 ? 1 : 0), 0);
            if (mx < cnt) {
                mx = cnt;
                ans = div;
            } else if (mx === cnt && ans > div) {
                ans = div;
            }
        }
        return ans;
    }
    
    
  • impl Solution {
        pub fn max_div_score(nums: Vec<i32>, divisors: Vec<i32>) -> i32 {
            let mut ans = divisors[0];
            let mut mx = 0;
    
            for &div in &divisors {
                let mut cnt = 0;
    
                for &n in &nums {
                    if n % div == 0 {
                        cnt += 1;
                    }
                }
    
                if cnt > mx || (cnt >= mx && div < ans) {
                    mx = cnt;
                    ans = div;
                }
            }
    
            ans
        }
    }
    

All Problems

All Solutions