# Maximize Number of Nice Divisors
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximize-number-of-nice-divisors)
Canonical: https://scaleengineer.com/dsa/problems/maximize-number-of-nice-divisors
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Recursion](https://scaleengineer.com/dsa/patterns/recursion), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
---
## Problem
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
## 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.
**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.
**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`).
### Explanation
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`.

```java
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];
    }
}
```
### 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`.

## Optimized Dynamic Programming
This approach improves upon the naive DP by observing a pattern in the optimal partitions. The optimal partitions are composed of only 2s and 3s. This simplifies the recurrence relation, leading to a linear time solution.
**Time:** O(primeFactors). We iterate once from 5 to `primeFactors`. · **Space:** O(primeFactors) for the DP table.
**Pros:** Much faster than the naive DP approach.
**Cons:** Still too slow and memory-intensive for the given constraints (`primeFactors <= 10^9`).
### Explanation
This approach improves upon the naive DP by observing a pattern in the optimal partitions. The optimal partitions are composed of only 2s and 3s. This simplifies the recurrence relation, leading to a linear time solution.

Mathematical analysis shows that to maximize the product for a given sum, the numbers in the partition should be small, specifically 2s and 3s. Any number `k >= 4` can be replaced by `2` and `k-2`, resulting in an equal or larger product (`2*(k-2) >= k`). This means to find the optimal product for `i`, we only need to consider breaking it down by subtracting 2 or 3. The recurrence relation becomes: `dp[i] = max(2 * dp[i-2], 3 * dp[i-3])`.

We still build a DP table from `i=1` up to `primeFactors`. The base cases need to be handled carefully: `dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=4`. The recurrence is valid for `i >= 5`. For example, `dp[5] = max(2 * dp[3], 3 * dp[2]) = max(2*3, 3*2) = 6`.

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

        for (int i = 5; i <= primeFactors; i++) {
            long option1 = (dp[i - 2] * 2) % MOD;
            long option2 = (dp[i - 3] * 3) % MOD;
            dp[i] = Math.max(option1, option2);
        }
        return (int) dp[primeFactors];
    }
}
```
### Algorithm
- Mathematical analysis shows that to maximize the product for a given sum, the numbers in the partition should be small, specifically 2s and 3s. This means to find the optimal product for `i`, we only need to consider breaking it down by subtracting 2 or 3.
- The recurrence relation becomes: `dp[i] = max(2 * dp[i-2], 3 * dp[i-3])`.
- We still build a DP table from `i=1` up to `primeFactors`.
- The base cases need to be handled carefully: `dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=4`. The recurrence is valid for `i >= 5`.
- For example, `dp[5] = max(2 * dp[3], 3 * dp[2]) = max(2*3, 3*2) = 6`.
- `dp[6] = max(2 * dp[4], 3 * dp[3]) = max(2*4, 3*3) = 9`.

## Mathematical Approach with Modular Exponentiation
This is the most efficient approach, leveraging mathematical insights to find a direct formula for the result. The problem is reduced to a simple calculation involving modular exponentiation, which can be computed in logarithmic time.
**Time:** O(log(primeFactors)). The dominant operation is the modular exponentiation, which takes logarithmic time with respect to the exponent. The exponent is proportional to `primeFactors`. · **Space:** O(1). The iterative implementation of modular exponentiation uses constant extra space.
**Pros:** Extremely efficient and fast.; Handles the largest possible inputs within the time limits.; Optimal solution.
**Cons:** Requires mathematical insight to derive the formula, which might not be immediately obvious.
### Explanation
This is the most efficient approach, leveraging mathematical insights to find a direct formula for the result. The problem is reduced to a simple calculation involving modular exponentiation, which can be computed in logarithmic time.

The core idea is to partition `primeFactors` into a sum of integers whose product is maximized. As established, the optimal partition consists of only 2s and 3s. Furthermore, since `3 * 3 > 2 * 2 * 2` (for a sum of 6, `9 > 8`), it's always better to use as many 3s as possible.

We can analyze the problem based on the remainder of `primeFactors` when divided by 3. Let `n = primeFactors`.
- **Case 1: `n % 3 == 0`**: The optimal partition is to use `n / 3` threes. The product is `3^(n/3)`.
- **Case 2: `n % 3 == 1`**: We can't have a `1` in the partition. We group one `3` and the `1` to make a `4`. The partition becomes `(k-1)` threes and one `4`, where `n = 3k+1`. The product is `3^(k-1) * 4`.
- **Case 3: `n % 3 == 2`**: The partition is `k` threes and one `2`, where `n = 3k+2`. The product is `3^k * 2`.

We handle small base cases `n <= 3` separately, where the answer is `n`. For `n > 3`, the above logic applies. Since the exponent can be very large, we must use modular exponentiation to compute `base^exp % MOD` efficiently.

```java
class Solution {
    long MOD = 1_000_000_007;

    private long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) {
                res = (res * base) % MOD;
            }
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }

    public int maxNiceDivisors(int primeFactors) {
        if (primeFactors <= 3) {
            return primeFactors;
        }
        
        long n = primeFactors;
        
        if (n % 3 == 0) {
            return (int) power(3, n / 3);
        } else if (n % 3 == 1) {
            // n = 3k + 1 = 3(k-1) + 4
            long exp = (n - 4) / 3;
            long p = power(3, exp);
            return (int) ((p * 4) % MOD);
        } else { // n % 3 == 2
            // n = 3k + 2
            long exp = (n - 2) / 3;
            long p = power(3, exp);
            return (int) ((p * 2) % MOD);
        }
    }
}
```
### Algorithm
- Define `MOD = 10^9 + 7`.
- Handle base cases: If `primeFactors <= 3`, return `primeFactors`.
- Let `n = primeFactors`.
- If `n % 3 == 0`, calculate and return `power(3, n/3, MOD)`.
- If `n % 3 == 1`, calculate `p = power(3, (n-4)/3, MOD)`. Return `(p * 4) % MOD`.
- If `n % 3 == 2`, calculate `p = power(3, (n-2)/3, MOD)`. Return `(p * 2) % MOD`.
- The `power` function should be implemented using modular exponentiation (exponentiation by squaring) for efficiency.

# Solutions
### Java

```java
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 ; } }
```

### JavaScript

```javascript
/** * @param {number} primeFactors * @return {number} */ var maxNiceDivisors = function ( primeFactors ) { if ( primeFactors < 4 ) { return primeFactors ; } const mod = 1 e9 + 7 ; const qpow = ( a , n ) => { let ans = 1 ; for (; n ; n >>= 1 ) { if ( n & 1 ) { ans = Number (( BigInt ( ans ) * BigInt ( a )) % BigInt ( mod )); } a = Number (( BigInt ( a ) * BigInt ( a )) % BigInt ( mod )); } return ans ; }; const k = Math . floor ( primeFactors / 3 ); if ( primeFactors % 3 === 0 ) { return qpow ( 3 , k ); } if ( primeFactors % 3 === 1 ) { return ( 4 * qpow ( 3 , k - 1 )) % mod ; } return ( 2 * qpow ( 3 , k )) % mod ; };

```

### CPP

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

### Python

```python
class Solution : def maxNiceDivisors ( self , primeFactors : int ) -> int : mod = 10 ** 9 + 7 if primeFactors < 4 : return primeFactors if primeFactors % 3 == 0 : return pow ( 3 , primeFactors // 3 , mod ) % mod if primeFactors % 3 == 1 : return 4 * pow ( 3 , primeFactors // 3 - 1 , mod ) % mod return 2 * pow ( 3 , primeFactors // 3 , mod ) % mod
```