algoadvance

Leetcode 2644. Find the Maximum Divisibility Score

Problem Statement

Given two integer arrays nums and divisors, return the divisor from divisors that has the maximum divisibility score. The divisibility score of a divisor is the number of elements in nums that are divisible by that divisor. If there is more than one divisor with the maximum score, return the smallest divisor.

Clarifying Questions

1. What are the constraints on the inputs?
   • Typical constraints would be helpful to know, such as the maximum length of nums and divisors and the range of the values within these arrays.
2. What should be returned if both nums and divisors are empty?
   • Clarifying an edge case where inputs might be empty can help in structuring our solution.
3. Can the elements in nums or divisors be negative?
   • This affects how we calculate divisibility.

Assumptions

• Based on common constraints, we can assume:
  • The lengths of nums and divisors are reasonable for an O(n * m) solution.
  • Elements in nums and divisors are non-negative integers (assuming divisors would typically be positive for common problems of this nature).

Strategy

1. Initialize Variables:
   • A variable to keep track of the maximum score.
   • A variable to keep the best candidate divisor with the maximum score.
2. Iterate Over Divisors:
   • For each divisor in the divisors list, count how many elements in nums are divisible by the divisor.
   • If the count for the current divisor is higher than our current maximum score, update the maximum score and set the current divisor as the best candidate.
   • If the count is equal to the current maximum score but the current divisor is smaller than the best candidate, update the best candidate.
3. Return the Best Candidate:
   • Finally, return the divisor with the maximum divisibility score or the smallest such divisor in case of ties.

Code

#include <vector>
#include <algorithm>
#include <climits>

int maxDivisibilityScore(const std::vector<int>& nums, const std::vector<int>& divisors) {
    int maxScore = 0;
    int bestDivisor = INT_MAX;

    for (int divisor : divisors) {
        int currentScore = 0;

        for (int num : nums) {
            if (num % divisor == 0) {
                currentScore++;
            }
        }

        if (currentScore > maxScore) {
            maxScore = currentScore;
            bestDivisor = divisor;
        } else if (currentScore == maxScore) {
            bestDivisor = std::min(bestDivisor, divisor);
        }
    }

    return bestDivisor;
}

Time Complexity

• Time Complexity: O(n * m), where n is the number of elements in nums and m is the number of elements in divisors.
  • This is because for each divisor, we inspect all elements in nums.
• Space Complexity: O(1)
  • We are using a constant amount of extra space regardless of the input size.

Explanation

1. Initialization:
   • The maxScore is initialized to 0 and bestDivisor to a very large value (INT_MAX) ensuring any real divisor will be smaller.
2. Main Loop:
   • For each divisor, we count how many numbers in nums are divisible by it.
   • If a divisor manages to get a higher count than the current maxScore, it becomes the bestDivisor and updates the maxScore.
   • If the count is equal, the smaller of the current bestDivisor and the current divisor is chosen.
3. Return:
   • The bestDivisor with the maximum score (or smallest in case of ties) is returned.

By following this strategy, we ensure that the solution is both correct and efficient within the provided constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?