Find the Maximum Divisibility Score solution and explanation
9 more videos on this problem
Leetcode 2644. Find the Maximum Divisibility Score | Contest 341 | Leetcode weekly contest SolutionOffCampus Phodenge | Aman Chowdhury · 12:24 · 345 views
2644. Find the Maximum Divisibility Score (Leetcode Medium)Programming Live with Larry · 3:57 · 275 views
Find the Maximum Divisibility Score - Leetcode 2644 - PythonAlgorithms Casts · 6:33 · 273 views
Leetcode Weekly contest 341 - Easy - Find the Maximum Divisibility ScorePrakhar Agrawal · 4:50 · 273 views
Leetcode Weekly Contest | 6350. Find the Maximum Divisibility Score | PythonBayu Aji · 2:53 · 175 views
leetcode 2644. Find the Maximum Divisibility Score - treat Multiple Occurence by set and dictCode-Yao · 10:13 · 53 views
Leetcode 6350. find the maximum divisibility score || Java solutionExpertFunda · 9:43 · 48 views
Leetcode 6350. Find the Maximum Divisibility Score || PART 1 Understanding || See Part 2 for codingExpertFunda · 5:57 · 45 views
LeetCode 2644 | Find the Maximum Divisibility Score | Easy Explained404DevFound · 5:02 · 23 views
L522, №2644. Find the Maximum Divisibility Score / LeetcodeYersham · 9:44 · 20 views
The 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 <= 10001 <= nums[i], divisors[i] <= 109
Approach overview
Problem Overview: You are given an integer array nums and another array divisors. For every divisor, count how many numbers in nums are divisible by it. The divisor with the highest count (divisibility score) is returned. If multiple divisors produce the same score, return the smallest divisor.
Approach 1: Naive Iterative Approach (O(n * m) time, O(1) space)
Loop through every value in divisors and compute its divisibility score by iterating through the nums array. For each pair, check num % divisor == 0. Maintain two variables: the best score seen so far and the corresponding smallest divisor that produced it. If a new divisor produces a larger score, update both values. If the score ties with the current maximum, keep the smaller divisor.
This method relies on straightforward iteration over arrays. The logic is simple and easy to implement in any language. Because every divisor checks every element in nums, the total work is proportional to len(nums) * len(divisors). Space usage stays constant since only counters and the result variable are stored.
Approach 2: Optimized Counting with Early Exit (O(n * m) worst-case time, O(1) space)
The counting logic stays the same, but the loop can terminate early when the current divisor can no longer beat the best score. While scanning nums, track the current score. If the remaining elements plus the current score cannot exceed the best score already found, break the loop early. This avoids unnecessary modulo checks for clearly worse candidates.
This optimization works well when the best divisor appears early or when divisibility is sparse. The algorithm still operates on array traversal and simple math operations such as modulo. Worst‑case complexity remains O(n * m), but practical runtime improves because many divisor checks terminate early.
Recommended for interviews: Start with the naive iterative approach. It clearly demonstrates the divisibility scoring logic and tie‑breaking rule. Then mention the early‑exit optimization to reduce unnecessary checks. Interviewers expect the straightforward O(n * m) scan because the constraints are small and the problem primarily tests careful iteration and condition handling.
Approach 1: Naive Iterative Approach
This approach involves iterating through each element in the divisors list and calculating the divisibility score by counting how many elements in the nums list are perfectly divisible by the current divisor. We maintain a variable to track the maximum score and update it as necessary. In the case of a tie, we select the smallest divisor.
def find_max_divisor(nums, divisors):
max_score, best_divisor = -1, float('inf')
for div in divisors:
score = sum(1 for num in nums if num % div == 0)
if score > max_score or (score == max_score and div < best_divisor):
max_score, best_divisor = score, div
return best_divisor
nums = [2, 9, 15, 50]
divisors = [5, 3, 7, 2]
print(find_max_divisor(nums, divisors)) # Output: 2import java.util.List;
public class Main {
public static int findMaxDivisor(List<Integer> nums, List<Integer> divisors) {
int maxScore = -1, bestDivisor = -1;
for (int div : divisors) {
int score = 0;
for (int num : nums) {
if (num % div == 0) {
score++;
}
}
if (score > maxScore || (score == maxScore && div < bestDivisor)) {
maxScore = score;
bestDivisor = div;
}
}
return bestDivisor;
}
public static void main(String[] args) {
List<Integer> nums = List.of(2, 9, 15, 50);
List<Integer> divisors = List.of(5, 3, 7, 2);
System.out.println(findMaxDivisor(nums, divisors)); // Output: 2
}
}#include <iostream>
#include <vector>
using namespace std;
int findMaxDivisor(const vector<int>& nums, const vector<int>& divisors) {
int maxScore = -1, bestDivisor = -1;
for (int div : divisors) {
int score = 0;
for (int num : nums) {
if (num % div == 0) {
score++;
}
}
if (score > maxScore || (score == maxScore && div < bestDivisor)) {
maxScore = score;
bestDivisor = div;
}
}
return bestDivisor;
}
int main() {
vector<int> nums = {2, 9, 15, 50};
vector<int> divisors = {5, 3, 7, 2};
cout << findMaxDivisor(nums, divisors) << endl; // Output: 2
return 0;
}function findMaxDivisor(nums, divisors) {
let maxScore = -1;
let bestDivisor = Number.MAX_SAFE_INTEGER;
divisors.forEach(div => {
let score = nums.reduce((count, num) => count + (num % div === 0 ? 1 : 0), 0);
if (score > maxScore || (score === maxScore && div < bestDivisor)) {
maxScore = score;
bestDivisor = div;
}
});
return bestDivisor;
}
const nums = [2, 9, 15, 50];
const divisors = [5, 3, 7, 2];
console.log(findMaxDivisor(nums, divisors)); // Output: 2#include <stdio.h>
int findMaxDivisor(int nums[], int numsSize, int divisors[], int divisorsSize) {
int maxScore = -1, bestDivisor = -1;
for (int i = 0; i < divisorsSize; i++) {
int score = 0;
for (int j = 0; j < numsSize; j++) {
if (nums[j] % divisors[i] == 0) {
score++;
}
}
if (score > maxScore || (score == maxScore && divisors[i] < bestDivisor)) {
maxScore = score;
bestDivisor = divisors[i];
}
}
return bestDivisor;
}
int main()
{
int nums[] = {2, 9, 15, 50};
int divisors[] = {5, 3, 7, 2};
int result = findMaxDivisor(nums, 4, divisors, 4);
printf("%d\n", result); // Output: 2
return 0;
}using System;
using System.Linq;
using System.Collections.Generic;
public class MaxDivisor {
public static int FindMaxDivisor(List<int> nums, List<int> divisors) {
int maxScore = -1, bestDivisor = -1;
foreach (int div in divisors) {
int score = nums.Count(num => num % div == 0);
if (score > maxScore || (score == maxScore && div < bestDivisor)) {
maxScore = score;
bestDivisor = div;
}
}
return bestDivisor;
}
public static void Main(string[] args) {
List<int> nums = new List<int> { 2, 9, 15, 50 };
List<int> divisors = new List<int> { 5, 3, 7, 2 };
Console.WriteLine(FindMaxDivisor(nums, divisors)); // Output: 2
}
}The Python solution leverages a generator expression within the sum function to compute divisibility scores for each divisor. It then follows the same comparison logic to track the maximum score and return the smallest numbering divisor when ties occur.
Time Complexity: O(n * m), where n and m are lengths of nums and divisors.
Space Complexity: O(1), no additional storage apart from inputs.
Approach 2: Optimized Counting with Early Exit
This approach enhances efficiency by seeking an early exit on obvious winners during processing. Instead of evaluating every divisor in a linear pass, we update our search to check if potential divisors far outweigh the best without scanning every nums element against it.
def find_max_divisor(nums, divisors):
max_score, best_divisor = -1, float('inf')
for div in divisors:
score = sum(1 for num in nums if num % div == 0)
if score > max_score or (score == max_score and div < best_divisor):
max_score, best_divisor = score, div
if max_score == len(nums):
break
return best_divisor
nums = [4, 7, 9, 3, 9]
divisors = [5, 2, 3]
print(find_max_divisor(nums, divisors)) # Output: 3import java.util.List;
public class Main {
public static int findMaxDivisor(List<Integer> nums, List<Integer> divisors) {
int maxScore = -1, bestDivisor = -1;
for (int div : divisors) {
int score = 0;
for (int num : nums) {
if (num % div == 0) {
score++;
if (score > maxScore) break;
}
}
if (score > maxScore || (score == maxScore && div < bestDivisor)) {
maxScore = score;
bestDivisor = div;
}
}
return bestDivisor;
}
public static void main(String[] args) {
List<Integer> nums = List.of(4, 7, 9, 3, 9);
List<Integer> divisors = List.of(5, 2, 3);
System.out.println(findMaxDivisor(nums, divisors)); // Output: 3
}
}#include <iostream>
#include <vector>
using namespace std;
int findMaxDivisor(const vector<int>& nums, const vector<int>& divisors) {
int maxScore = -1, bestDivisor = -1;
for (int div : divisors) {
int score = 0;
for (int num : nums) {
if (num % div == 0) {
score++;
if (score > maxScore) break;
}
}
if (score > maxScore || (score == maxScore && div < bestDivisor)) {
maxScore = score;
bestDivisor = div;
}
}
return bestDivisor;
}
int main() {
vector<int> nums = {4, 7, 9, 3, 9};
vector<int> divisors = {5, 2, 3};
cout << findMaxDivisor(nums, divisors) << endl; // Output: 3
return 0;
}function findMaxDivisor(nums, divisors) {
let maxScore = -1;
let bestDivisor = Number.MAX_SAFE_INTEGER;
divisors.forEach(div => {
let score = nums.reduce((count, num) => count + (num % div === 0 ? 1 : 0), 0);
if (score > maxScore || (score === maxScore && div < bestDivisor)) {
maxScore = score;
bestDivisor = div;
}
if (maxScore === nums.length) {
return bestDivisor;
}
});
return bestDivisor;
}
const nums = [4, 7, 9, 3, 9];
const divisors = [5, 2, 3];
console.log(findMaxDivisor(nums, divisors)); // Output: 3#include <stdio.h>
int findMaxDivisor(int nums[], int numsSize, int divisors[], int divisorsSize) {
int maxScore = -1, bestDivisor = -1;
for (int i = 0; i < divisorsSize; i++) {
int div = divisors[i], score = 0;
for (int j = 0; j < numsSize; j++) {
if (nums[j] % div == 0) {
score++;
if (score > maxScore) break;
}
}
if (score > maxScore || (score == maxScore && div < bestDivisor)) {
maxScore = score;
bestDivisor = div;
}
}
return bestDivisor;
}
int main()
{
int nums[] = {4, 7, 9, 3, 9};
int divisors[] = {5, 2, 3};
int result = findMaxDivisor(nums, 5, divisors, 3);
printf("%d\n", result); // Output: 3
return 0;
}using System;
using System.Linq;
using System.Collections.Generic;
public class MaxDivisor {
public static int FindMaxDivisor(List<int> nums, List<int> divisors) {
int maxScore = -1, bestDivisor = -1;
foreach (int div in divisors) {
int score = nums.Count(num => num % div == 0);
if (score > maxScore || (score == maxScore && div < bestDivisor)) {
maxScore = score;
bestDivisor = div;
}
if (maxScore == nums.Count) {
break;
}
}
return bestDivisor;
}
public static void Main(string[] args) {
List<int> nums = new List<int> { 4, 7, 9, 3, 9 };
List<int> divisors = new List<int> { 5, 2, 3 };
Console.WriteLine(FindMaxDivisor(nums, divisors)); // Output: 3
}
}Here, Python's version prioritizes sharp logic by inserting reasoning about realism in dominating scores, unifying the decision sequence under improved stopping checks. Immediate dispatch on detecting maximality showcases aware processing underlying complexity bounds.
Time Complexity: O(n * m), possible early stopping.
Space Complexity: O(1).
Approach 3: Enumeration
We can enumerate each element div in divisors, and calculate how many elements in nums can be divided by div, denoted as cnt.
- If
cntis greater than the current maximum divisibility scoremx, then updatemx = cnt, and updateans = div. - If
cntequalsmxanddivis less thanans, then updateans = div.
Finally, return ans.
The time complexity is O(m times n), where m and n are the lengths of nums and divisors respectively. The space complexity is O(1).
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;
}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
}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
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Naive Iterative Approach | Time Complexity: |
| Optimized Counting with Early Exit | Time Complexity: |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Iterative Approach | O(n * m) | O(1) | General case. Simple implementation when input sizes are moderate. |
| Optimized Counting with Early Exit | O(n * m) worst case | O(1) | When many divisors quickly become worse candidates and loops can terminate early. |
Frequently asked questions
Is Find the Maximum Divisibility Score easy or hard?
Find the Maximum Divisibility Score is classified as an Easy problem. The core logic involves basic array traversal and counting divisible elements. The only tricky part is handling the tie condition by selecting the smallest divisor.
Find the Maximum Divisibility Score Python/Java solution
The implementation in Python or Java loops through each divisor and counts how many elements in nums satisfy num % divisor == 0. Maintain variables for the best score and the smallest divisor producing that score. This results in O(n * m) time and constant extra space.
How to solve Find the Maximum Divisibility Score in O(n)?
A strict O(n) solution is generally not possible because every divisor must be evaluated to compute its score. The optimal practical approach scans nums for each divisor, resulting in O(n * m) time. Minor optimizations such as early exit during counting can reduce unnecessary checks.
What is the best approach for Find the Maximum Divisibility Score?
The most practical approach iterates through each divisor and counts how many numbers in the nums array are divisible by it. Track the maximum score and return the smallest divisor when scores tie. This runs in O(n * m) time where n is the length of nums and m is the number of divisors, with O(1) extra space.
Is Find the Maximum Divisibility Score asked at Google/Amazon/Meta?
Problems involving divisibility checks and array iteration appear frequently in coding interviews at large tech companies. While this exact problem may not always appear, similar tasks testing array traversal, modulo operations, and tie‑breaking logic are common in interviews at companies like Amazon and Google.
What data structure is used in Find the Maximum Divisibility Score?
The problem primarily uses arrays for both nums and divisors. The algorithm relies on sequential traversal and simple arithmetic operations such as modulo. No advanced data structures are required.
What is the time complexity of Find the Maximum Divisibility Score?
The typical solution runs in O(n * m) time because each divisor checks divisibility against every element in nums. Space complexity is O(1) since only counters and result variables are used. Early termination optimizations can reduce runtime in practice but do not change the worst‑case complexity.