Maximize Number of Nice Divisors

HARD

Description

You are given a positive integer primeFactors. You are asked to construct a positive integer n that satisfies the following conditions:

The number of prime factors of n (not necessarily distinct) is at most primeFactors.
The number of nice divisors of n is maximized. Note that a divisor of n is nice if it is divisible by every prime factor of n. For example, if n = 12, then its prime factors are [2,2,3], then 6 and 12 are nice divisors, while 3 and 4 are not.

Return the number of nice divisors of n. Since that number can be too large, return it modulo 10⁹ + 7.

Note that a prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. The prime factors of a number n is a list of prime numbers such that their product equals n.

Example 1:

Input: primeFactors = 5
Output: 6
Explanation: 200 is a valid value of n.
It has 5 prime factors: [2,2,2,5,5], and it has 6 nice divisors: [10,20,40,50,100,200].
There is not other value of n that has at most 5 prime factors and more nice divisors.

Example 2:

Input: primeFactors = 8
Output: 18

Constraints:

1 <= primeFactors <= 10⁹

Approaches

Checkout 3 different approaches to solve Maximize Number of Nice Divisors. Click on different approaches to view the approach and algorithm in detail.

Dynamic Programming

This approach uses dynamic programming to solve the problem. We define dp[i] as the maximum product we can get by partitioning the integer i. We build up the solution for primeFactors from the solutions for smaller numbers.

Algorithm

The problem is to partition an integer n = primeFactors into a sum of positive integers a1, a2, ... ak such that their product is maximized.
Let dp[i] be the maximum product for a partition of i.
To compute dp[i], we can consider splitting i into two parts, j and i-j. The maximum product for i would then be the maximum of dp[j] * dp[i-j] over all possible j from 1 to i/2.
We also need to consider the case where i is not partitioned at all. So, the recurrence relation is: dp[i] = max(i, max_{1 <= j <= i/2} (dp[j] * dp[i-j]))
We can build a table dp from i=1 up to primeFactors.
The base cases are dp[1]=1, dp[2]=2, dp[3]=3.
For example, dp[4] = max(4, dp[1]*dp[3], dp[2]*dp[2]) = max(4, 1*3, 2*2) = 4.
dp[5] = max(5, dp[1]*dp[4], dp[2]*dp[3]) = max(5, 1*4, 2*3) = 6.
The final answer is dp[primeFactors]. All calculations should be done modulo 10^9 + 7.

The problem is to partition an integer n = primeFactors into a sum of positive integers a1, a2, ... ak such that their product is maximized. Let dp[i] be the maximum product for a partition of i. To compute dp[i], we can consider splitting i into two parts, j and i-j. The maximum product for i would then be the maximum of dp[j] * dp[i-j] over all possible j from 1 to i/2. We also need to consider the case where i is not partitioned at all. So, the recurrence relation is: dp[i] = max(i, max_{1 <= j <= i/2} (dp[j] * dp[i-j]))

We can build a table dp from i=1 up to primeFactors. The base cases are dp[1]=1, dp[2]=2, dp[3]=3. For example, dp[4] = max(4, dp[1]*dp[3], dp[2]*dp[2]) = max(4, 1*3, 2*2) = 4. The final answer is dp[primeFactors]. All calculations should be done modulo 10^9 + 7.

class Solution {
    public int maxNiceDivisors(int primeFactors) {
        if (primeFactors <= 3) {
            return primeFactors;
        }
        long[] dp = new long[primeFactors + 1];
        long MOD = 1_000_000_007;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;

        for (int i = 4; i <= primeFactors; i++) {
            dp[i] = i; // Option to not partition
            for (int j = 1; j <= i / 2; j++) {
                long product = (dp[j] * dp[i - j]) % MOD;
                if (product > dp[i]) {
                    dp[i] = product;
                }
            }
        }
        return (int) dp[primeFactors];
    }
}

Complexity Analysis

Time Complexity: O(primeFactors^2). The outer loop runs `primeFactors` times, and the inner loop runs `primeFactors/2` times in the worst case.Space Complexity: O(primeFactors) to store the DP table.

Pros and Cons

Pros:

Conceptually simple to understand if familiar with DP.
Correct for small values of primeFactors.

Cons:

Exceeds time and memory limits for the given constraints (primeFactors <= 10^9).

Code Solutions

Checking out 4 solutions in different languages for Maximize Number of Nice Divisors. Click on different languages to view the code.

class Solution { private final int mod = ( int ) 1 e9 + 7 ; public int maxNiceDivisors ( int primeFactors ) { if ( primeFactors < 4 ) { return primeFactors ; } if ( primeFactors % 3 == 0 ) { return qpow ( 3 , primeFactors / 3 ); } if ( primeFactors % 3 == 1 ) { return ( int ) ( 4L * qpow ( 3 , primeFactors / 3 - 1 ) % mod ); } return 2 * qpow ( 3 , primeFactors / 3 ) % mod ; } private int qpow ( long a , long n ) { long ans = 1 ; for (; n > 0 ; n >>= 1 ) { if (( n & 1 ) == 1 ) { ans = ans * a % mod ; } a = a * a % mod ; } return ( int ) ans ; } }

Video Solution

Watch the video walkthrough for Maximize Number of Nice Divisors

Patterns:

MathRecursionNumber Theory