Find the Maximum Divisibility Score - Practice Coding Problems

Find the Maximum Divisibility Score - Problem

Array Easy

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [4,7,9,3,9], divisors = [5,2,3]

› Output: 3

💡 Note: Divisor 5: no numbers divisible (score 0). Divisor 2: only 4 is divisible (score 1). Divisor 3: numbers 9, 3, 9 are divisible (score 3). Maximum score is 3, so return 3.

Example 2 — Tie Case

$ Input: nums = [20,14,21,10], divisors = [5,7,5]

› Output: 5

💡 Note: Divisor 5: numbers 20, 10 are divisible (score 2). Divisor 7: numbers 14, 21 are divisible (score 2). Both have score 2, but 5 < 7, so return 5.

Example 3 — Single Element

$ Input: nums = [12], divisors = [10,16]

› Output: 10

💡 Note: Divisor 10: 12 is not divisible by 10 (score 0). Divisor 16: 12 is not divisible by 16 (score 0). Both have score 0, but 10 < 16, so return 10.

Constraints

1 ≤ nums.length, divisors.length ≤ 1000
1 ≤ nums[i], divisors[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

nums array and divisors array

Count Scores

For each divisor, count how many numbers are divisible

Find Maximum

Return divisor with highest score (smallest if tied)

Key Takeaway

🎯 Key Insight: Count how many numbers each divisor can divide, return the divisor with the highest count

Asked in

G Google 25 M Microsoft 20 a Amazon 18

The key insight is to count divisibility for each divisor and track the maximum score. For ties, return the smallest divisor. The optimal approach uses O(n×m) time to check each divisor against all numbers, with O(1) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass Optimization	O(n × m)	O(1)	Track the best divisor while counting to avoid storing all scores
Brute Force	O(n × m)	O(1)	For each divisor, count how many numbers in nums are divisible by it

Single Pass Optimization — Algorithm Steps

Initialize max_score = -1 and best_divisor = infinity
For each divisor, count divisible numbers
Update best_divisor if score is higher or equal with smaller divisor
Return the best divisor found

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Divisor 3

Count score=3, update best_divisor=3

Process Divisor 2

Count score=1, keep best_divisor=3 (3 > 1)

Process Divisor 8

Count score=0, keep best_divisor=3 (3 > 0)

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* nums, int numsSize, int* divisors, int divisorsSize) {
    int maxScore = -1;
    int bestDivisor = INT_MAX;
    
    for (int i = 0; i < divisorsSize; i++) {
        int divisor = divisors[i];
        int score = 0;
        for (int j = 0; j < numsSize; j++) {
            if (nums[j] % divisor == 0) {
                score++;
            }
        }
        
        if (score > maxScore || (score == maxScore && divisor < bestDivisor)) {
            maxScore = score;
            bestDivisor = divisor;
        }
    }
    
    return bestDivisor;
}

int main() {
    char line1[10000], line2[10000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    int nums[1000], divisors[1000];
    int numsSize = 0, divisorsSize = 0;
    
    char* token = strtok(line1 + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    token = strtok(line2 + 1, ",]");
    while (token != NULL) {
        divisors[divisorsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, numsSize, divisors, divisorsSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

Still need to check each divisor against all numbers in nums

✓ Linear Growth

Space Complexity

O(1)

Only storing max_score and best_divisor variables

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler