We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Maximum Divisibility Score

Number: 2694

Difficulty: Easy

Paid? No

Companies: Amazon, DE Shaw

Problem Description

Given two integer arrays, nums and divisors, compute the divisibility score for each element in divisors, where the score is defined as the count of numbers in nums that are divisible by that divisor. Return the divisor with the maximum score. In the event of a tie, return the smallest divisor.

Key Insights

  • Iterate over each divisor and count how many numbers in nums are divisible by it.
  • Since both arrays are at most 1000 in length, a simple double loop (brute force) is efficient.
  • Maintain a record of the maximum score and update the candidate divisor accordingly.
  • Ensure to handle ties by choosing the smallest divisor when scores are equal.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of divisors and m is the length of nums.
Space Complexity: O(1), as only a few additional variables are used.

Solution

The solution involves iterating through each divisor in the divisors array and, for each one, iterating through the nums array to count how many elements are divisible by it. Keep track of the highest count (divisibility score) and update the answer if a higher score is found. In case of a tie, select the smaller divisor. This direct approach leverages simple loops and conditional comparisons, ensuring clarity and correctness within the given constraints.

Code Solutions

# Python solution with line-by-line comments

def maxDivScore(nums, divisors):
    # Initialize variables to track the best divisor and maximum score
    best_divisor = None
    max_score = -1
    
    # Iterate through each divisor in the divisors list
    for divisor in divisors:
        # Count how many numbers in nums are divisible by the current divisor
        score = sum(1 for num in nums if num % divisor == 0)
        
        # If the current score is higher than max_score or equal but with a smaller divisor
        if score > max_score or (score == max_score and (best_divisor is None or divisor < best_divisor)):
            max_score = score
            best_divisor = divisor
    
    # Return the divisor with the maximum divisibility score
    return best_divisor

# Example usage:
nums = [2,9,15,50]
divisors = [5,3,7,2]
print(maxDivScore(nums, divisors))  # Expected output: 2
← Back to All Questions