Find the Maximum Divisibility Score

Easy

Asked by:

14 views

Topics:

Arrays

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 <= 1000
1 <= nums[i], divisors[i] <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges and data types for the values in the `nums` and `divisors` arrays? Specifically, can they contain negative numbers, zeros, or floating-point numbers?
What are the size constraints on the `nums` and `divisors` arrays? Are they guaranteed to be non-empty?
If no element in `nums` is divisible by any element in `divisors`, what should the function return?
Are there any duplicate values within the `divisors` array, and if so, how should they be handled? Should I treat duplicate divisors as distinct for calculating the divisibility score?
In the case of a tie in the maximum divisibility score, is it guaranteed that there will be a single smallest divisor, or could there be multiple smallest divisors with the same maximum divisibility score?

Brute Force Solution

Approach

The brute force approach to finding the maximum divisibility score means we try every possible number from the divisors and count how many numbers in the given number list it divides. We then pick the divisor with the highest count.

Here's how the algorithm would work step-by-step:

Go through each number in the divisor list one by one.
For each number in the divisor list, go through every number in the given number list.
Check if the number from the divisor list perfectly divides the number from the given number list.
If it does, increase the count for that specific divisor.
Once we have checked all the numbers against the current divisor, store the count for that divisor.
After checking all divisors, compare the counts for each divisor.
Find the divisor that resulted in the highest count. That divisor is our answer.
If multiple divisors have the same highest count, pick the smallest among them.

Code Implementation

def find_max_divisibility_score_brute_force(numbers, divisors):
    maximum_score = -1
    best_divisor = -1

    for current_divisor in divisors:
        current_score = 0

        # Iterate through each number to calculate score
        for number_to_check in numbers:
            if number_to_check % current_divisor == 0:
                current_score += 1

        # If current score is greater, update the best divisor
        if current_score > maximum_score:
            maximum_score = current_score
            best_divisor = current_divisor

        # If scores are equal, choose the smallest divisor
        elif current_score == maximum_score:
            #Ensure we select the SMALLEST value
            best_divisor = min(best_divisor, current_divisor)

    return best_divisor

Big(O) Analysis

Time Complexity

O(n*m) – The provided brute force approach involves iterating through each of the m divisors and for each divisor, iterating through all n numbers in the input array to check for divisibility. Therefore, for each of the m divisors, we perform n divisibility checks. This results in a total of approximately m*n operations. Thus, the time complexity is O(n*m), where n is the size of the input number list and m is the number of divisors.

Space Complexity

O(1) – The brute force approach, as described, iterates through the divisors and numbers, keeping track of a count for each divisor. It appears the described algorithm overwrites the count variable for each divisor instead of storing the counts of each divisor in a separate data structure (like a list or hash map). Also, the algorithm stores the highest count and the corresponding divisor. Since only a few scalar variables are used (count, highest count, best divisor), and their number does not depend on the size of the input lists, the space complexity is constant.

Optimal Solution

Approach

To efficiently find the maximum divisibility score, we count how many numbers in the input list are divisible by each number in the divisors list. Then, we identify the divisor with the highest count (the maximum divisibility score). If there's a tie, we choose the smallest divisor.

Here's how the algorithm would work step-by-step:

Go through each number in the divisors list, one at a time.
For each divisor, go through every number in the input list and check if it's perfectly divisible by the current divisor. Keep a count of how many numbers are divisible.
After checking all numbers in the input list for a specific divisor, store the divisibility score for that divisor.
Once you've calculated the divisibility score for all divisors, find the highest score.
If multiple divisors have the same highest score, pick the smallest divisor among them. This is the final answer.

Code Implementation

def find_max_divisibility_score(numbers, divisors):
    maximum_score = -1
    best_divisor = -1

    for current_divisor in divisors:
        divisibility_score = 0

        # Calculate the score for the current divisor.
        for number in numbers:
            if number % current_divisor == 0:
                divisibility_score += 1

        # If a better score is found, update the best divisor.
        if divisibility_score > maximum_score:
            maximum_score = divisibility_score
            best_divisor = current_divisor
        # Tiebreaker: Choose the smaller divisor.
        elif divisibility_score == maximum_score:
            if current_divisor < best_divisor:
                best_divisor = current_divisor

    return best_divisor

Big(O) Analysis

Time Complexity

O(n*m) – The outer loop iterates through each of the 'm' divisors. The inner loop iterates through each of the 'n' numbers in the input list to check for divisibility by the current divisor. The divisibility check itself is a constant time operation. Therefore, the total number of operations is proportional to n multiplied by m. Thus, the time complexity is O(n*m).

Space Complexity

O(1) – The algorithm iterates through the divisors and nums lists, calculating the divisibility score for each divisor. It only needs to store a few variables: the current divisibility score, the maximum score found so far, and the corresponding divisor. Since the space used by these variables does not scale with the size of the input lists (divisors and nums), the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
nums is null or empty	Return -1 or throw an exception as there are no numbers to check for divisibility.
divisors is null or empty	Return -1 as there are no divisors to check against the nums array.
nums and divisors are both empty	Return -1 as there are no divisors or numbers to compare.
nums contains zero values	Divisors should not be zero, but zero can be divisible by non-zero values, which needs to be accounted in count.
divisors contains zero	Ignore divisors equal to zero since division by zero is undefined.
nums contains large integer values potentially leading to overflow	The division operation itself shouldn't cause an overflow as long as divisors are also integers, so no special handling is needed, assuming integer division is used.
All numbers in nums are the same and divisible by all numbers in divisors	The solution should iterate through the divisors and return the smallest divisor with the maximum divisibility score.
Large input arrays for nums and divisors (performance considerations)	Ensure the solution iterates efficiently through the arrays to avoid exceeding time limits, potentially using optimized loops or early termination strategies.

nums is null or empty

How to Handle:

Return -1 or throw an exception as there are no numbers to check for divisibility.

divisors is null or empty

How to Handle:

Return -1 as there are no divisors to check against the nums array.

nums and divisors are both empty

How to Handle:

Return -1 as there are no divisors or numbers to compare.

nums contains zero values

How to Handle:

Divisors should not be zero, but zero can be divisible by non-zero values, which needs to be accounted in count.

divisors contains zero

How to Handle:

Ignore divisors equal to zero since division by zero is undefined.

nums contains large integer values potentially leading to overflow

How to Handle:

The division operation itself shouldn't cause an overflow as long as divisors are also integers, so no special handling is needed, assuming integer division is used.

All numbers in nums are the same and divisible by all numbers in divisors

How to Handle:

The solution should iterate through the divisors and return the smallest divisor with the maximum divisibility score.

Large input arrays for nums and divisors (performance considerations)

How to Handle:

Ensure the solution iterates efficiently through the arrays to avoid exceeding time limits, potentially using optimized loops or early termination strategies.