Scale Engineer

Maximize Number of Nice Divisors

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

Prompt

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 109 + 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 <= 109

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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.

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

Time

O(primeFactors^2). The outer loop runs `primeFactors` times, and the inner loop runs `primeFactors/2` times in the worst case.

Space

O(primeFactors) to store the DP table.

Trade-offs

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).

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem