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

Maximize Number of Nice Divisors

Number: 1936

Difficulty: Hard

Paid? No

Companies: Microsoft

Problem Description

We are given a positive integer primeFactors. We need to construct a positive integer n such that:

  • The total number of prime factors of n (counted with multiplicity) is at most primeFactors.
  • n has as many "nice" divisors as possible. A divisor d of n is defined as nice if it is divisible by every prime factor that appears in the prime factorization of n. For example, if n = 12, whose prime factors (with multiplicity) are [2, 2, 3], then a divisor d is nice if it is divisible by 2 and by 3. For n = 12, the numbers 6 and 12 are nice divisors while 3 and 4 are not.

Return the maximum number of nice divisors modulo 10^9+7.

Key Insights

  • In the prime factorization n = p1^(e1) * p2^(e2) * ... * pk^(ek), a divisor is nice if it includes at least one copy of each prime. Therefore, the number of nice divisors equals e1 * e2 * ... * ek.
  • Given that we can use at most primeFactors primes (i.e. e1 + e2 + ... + ek <= primeFactors), our task reduces to partitioning the integer primeFactors into positive integers (each representing an exponent) so that their product is maximized.
  • It is a classic result that, to maximize product under a fixed sum, one should break the sum into numbers as close to 3 as possible—except that when the remainder is 1, it is better to use 4 (i.e. 2+2) instead of 3+1.
  • Thus, if we let S = primeFactors then:
    • If S mod 3 == 0, answer = 3^(S/3) mod (10^9+7).
    • If S mod 3 == 1, answer = 3^(S/3 - 1) * 4 mod (10^9+7).
    • If S mod 3 == 2, answer = 3^(S/3) * 2 mod (10^9+7).

Space and Time Complexity

Time Complexity: O(log(primeFactors)) due to the modular exponentiation. Space Complexity: O(1).

Solution

We first realize that we want to maximize the product of the exponents under the sum constraint primeFactors. This is the classical “integer break” or “maximum product partition” problem. We choose numbers of 3 as much as possible because they yield the best product. When the remainder is 1, replace one group of 3 with two 2’s (which is equivalent to multiplying by 4 instead of 3*1). The resulting formula is:

  • If primeFactors mod 3 == 0, then answer = 3^(primeFactors/3).
  • If primeFactors mod 3 == 1, then answer = 3^(primeFactors/3 - 1) * 4.
  • If primeFactors mod 3 == 2, then answer = 3^(primeFactors/3) * 2. We use modular exponentiation to compute the powers of 3 mod (10^9+7).

Code Solutions

# Python code with line-by-line comments
MOD = 10**9 + 7

def maxNiceDivisors(primeFactors):
    # if primeFactors is small, handle it directly
    if primeFactors <= 3:
        return primeFactors
    
    # compute the number of groups of 3 we can have and the remainder
    groups = primeFactors // 3
    remainder = primeFactors % 3
    
    # if no remainder, simply return 3^(groups) modulo MOD
    if remainder == 0:
        return pow(3, groups, MOD)
    # if remainder is 1, reduce one group of 3 to form 4 (i.e. 2+2 instead of 3+1)
    if remainder == 1:
        return (pow(3, groups - 1, MOD) * 4) % MOD
    # if remainder is 2, just multiply by 2
    return (pow(3, groups, MOD) * 2) % MOD

# Example usage
print(maxNiceDivisors(5))  # Output should be 6
print(maxNiceDivisors(8))  # Output should be 18
← Back to All Questions