Find the Maximum Divisibility Score

Easy
697.

Find the Maximum Divisibility Score

Find the Maximum Divisibility Score is an easy coding problem on arrays, math and counting, asked in Adobe, TCS and Infosys interviews.

The divisibility score of a candidate d is the number of entries in nums that d divides exactly.

Return the divisor with the highest score. If several tie, return the smallest of them.

Example 1

Input
nums = [4,7,9,3,9], divisors = [5,2,3]
Output
3
Explanation
3 divides 9, 3 and 9 for a score of 3, beating 2 (one hit) and 5 (none).

Example 2

Input
nums = [20,14,21,10], divisors = [5,7,5]
Output
5
Explanation
5 and 7 both score 2, so the smaller wins.

Example 3

Input
nums = [12], divisors = [10,16]
Output
10
Explanation
Neither divides 12, so both score 0 and the smaller wins.

Constraints

  • 1 <= nums.length, divisors.length <= 1000
  • 1 <= nums[i], divisors[i] <= 1000000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number[]} divisors
 * @return {number}
 */
var maxDivScore = function(nums, divisors) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the Maximum Divisibility Score — Problem & Solution

Find the Maximum Divisibility Score solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Find the Maximum Divisibility Score is an easy coding problem on arrays, math and counting, asked in Adobe, TCS and Infosys interviews.

  • Difficulty: Easy
  • Topics: Arrays, Math, Counting
  • Asked at: Adobe, TCS, Infosys
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

The divisibility score of a candidate d is the number of entries in nums that d divides exactly.

Return the divisor with the highest score. If several tie, return the smallest of them.

Example 1

Input: nums = [4,7,9,3,9], divisors = [5,2,3]
Output: 3
Explanation: 3 divides 9, 3 and 9 for a score of 3, beating 2 (one hit) and 5 (none).

Example 2

Input: nums = [20,14,21,10], divisors = [5,7,5]
Output: 5
Explanation: 5 and 7 both score 2, so the smaller wins.

Example 3

Input: nums = [12], divisors = [10,16]
Output: 10
Explanation: Neither divides 12, so both score 0 and the smaller wins.

Constraints

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

Hints for Find the Maximum Divisibility Score

  1. Hint 1

    Score every divisor by a full pass over nums.

  2. Hint 2

    Keep the running best, and on a tie prefer the smaller divisor.

  3. Hint 3

    A score of zero is legitimate — the answer is then the smallest divisor overall.

How to solve Find the Maximum Divisibility Score

There is nothing clever to do: score each divisor directly and keep the best under the stated tie-break.

Approach

  1. For each divisor d, count how many entries of nums satisfy x % d == 0.
  2. Adopt d when its score beats the best so far, or ties it while being smaller.

Why it works

The comparison 'higher score, then smaller value' is a strict total order on the candidates, so a single sweep keeping the maximum under that order finds the unique answer.

Complexity

  • Time — O(n · m)
  • Space — O(1)

Pitfalls

  • Initialising the best score to 0 rather than -1 makes an all-zero input return whichever divisor came first rather than the smallest.
  • Duplicated divisors are harmless — they tie with themselves.

Reference solution

Python

from typing import List

def maxDivScore(nums: List[int], divisors: List[int]) -> int:
    best_div = 0
    best_score = -1
    for d in divisors:
        score = sum(1 for x in nums if x % d == 0)
        if score > best_score or (score == best_score and d < best_div):
            best_score = score
            best_div = d
    return best_div

Java

public static int maxDivScore(int[] nums, int[] divisors) {
    int bestDiv = 0, bestScore = -1;
    for (int d : divisors) {
        int score = 0;
        for (int x : nums) {
            if (x % d == 0) score++;
        }
        if (score > bestScore || (score == bestScore && d < bestDiv)) { bestScore = score; bestDiv = d; }
    }
    return bestDiv;
}

C++

int maxDivScore(vector<int>& nums, vector<int>& divisors) {
    int bestDiv = 0, bestScore = -1;
    for (int d : divisors) {
        int score = 0;
        for (int x : nums) {
            if (x % d == 0) score++;
        }
        if (score > bestScore || (score == bestScore && d < bestDiv)) { bestScore = score; bestDiv = d; }
    }
    return bestDiv;
}

JavaScript

var maxDivScore = function(nums, divisors) {
    var bestDiv = 0, bestScore = -1;
    for (var i = 0; i < divisors.length; i++) {
        var d = divisors[i], score = 0;
        for (var j = 0; j < nums.length; j++) {
            if (nums[j] % d === 0) score++;
        }
        if (score > bestScore || (score === bestScore && d < bestDiv)) { bestScore = score; bestDiv = d; }
    }
    return bestDiv;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays