 # Leetcode 1808. Maximize Number of Nice Divisors Solution

## Problem Explanation

You are given a positive integer `primeFactors`. Your task is to construct a positive integer `n` that satisfies the following conditions:

1. The number of prime factors of n (not necessarily distinct) is at most `primeFactors`.
2. The number of nice divisors of `n` is maximized. A divisor of `n` is considered nice if it is divisible by every prime factor of `n`.

The goal is to return the number of nice divisors of `n`. However, since the number could be very large, return the result modulo 10^9 + 7.

The key to solving this problem lies in realizing that the optimal `n` can be formed by having as many small prime factors as possible. Therefore, maximizing the number of nice divisors with a limited number of prime factors means using smaller prime numbers as factors, namely 2 and 3.

Let's walk through an example to understand the approach better.

### Example

Input: primeFactors = 5

To maximize the number of nice divisors, we can choose `n` to be 200.

``````1Prime factors of 200: [2, 2, 2, 5, 5]
2
3Nice divisors of 200: [10, 20, 40, 50, 100, 200]``````

The output would be 6, as there are 6 nice divisors of 200.

## Approach

1. If `primeFactors` is less than or equal to 3, return `primeFactors` as no distribution of prime factors can create a higher number of nice divisors.
2. If `primeFactors` is divisible by 3, return `myPow(3, primeFactors / 3) % kMod` because the optimal distribution of prime factors can be achieved using only 3's.
3. If `primeFactors % 3 == 1`, return `4L * myPow(3, (primeFactors - 4) / 3) % kMod` because the optimal distribution can be achieved with one 2 and the rest being 3's.
4. If `primeFactors % 3 == 2`, return `2L * myPow(3, (primeFactors - 2) / 3) % kMod` because the optimal distribution can be achieved with two 2's and the rest being 3's.

### C++ Solution

``````1class Solution {
2public:
3    int maxNiceDivisors(int primeFactors) {
4        if (primeFactors <= 3)
5            return primeFactors;
6
7        long kMod = 1000000007;
8
9        if (primeFactors % 3 == 0)
10            return myPow(3, primeFactors / 3, kMod) % kMod;
11        if (primeFactors % 3 == 1)
12            return (4L * myPow(3, (primeFactors - 4) / 3, kMod)) % kMod;
13        return (2L * myPow(3, (primeFactors - 2) / 3, kMod)) % kMod;
14    }
15
16    long myPow(long x, int n, int kMod) {
17        if (n == 0)
18            return 1;
19        if (n % 2 == 1)
20            return x * myPow(x, n - 1, kMod) % kMod;
21        return myPow((x * x) % kMod, n / 2, kMod);
22    }
23};``````

### Python Solution

``````1class Solution:
2    def maxNiceDivisors(self, primeFactors: int) -> int:
3        if primeFactors <= 3:
4            return primeFactors
5
6        kMod = 1000000007
7        pow3 = pow(3, primeFactors // 3, kMod)
8
9        if primeFactors % 3 == 0:
10            return pow3 % kMod
11        if primeFactors % 3 == 1:
12            return (4 * pow(3, (primeFactors - 4) // 3, kMod)) % kMod
13        return (2 * pow(3, (primeFactors - 2) // 3, kMod)) % kMod``````

### Java Solution

``````1class Solution {
2    public int maxNiceDivisors(int primeFactors) {
3        if (primeFactors <= 3) {
4            return primeFactors;
5        }
6
7        int kMod = 1000000007;
8
9        if (primeFactors % 3 == 0) {
10            return (int)((long)myPow(3, primeFactors / 3, kMod) % kMod);
11        }
12        if (primeFactors % 3 == 1) {
13            return (int)((4L * myPow(3, (primeFactors - 4) / 3, kMod)) % kMod);
14        }
15        return (int)((2L * myPow(3, (primeFactors - 2) / 3, kMod)) % kMod);
16    }
17
18    private int myPow(int x, int n, int kMod) {
19        if (n == 0) {
20            return 1;
21        }
22        if (n % 2 == 1) {
23            return (int)(((long)x * myPow(x, n - 1, kMod)) % kMod);
24        }
25        return myPow((int)((long)x * x % kMod), n / 2, kMod);
26    }
27}``````

### JavaScript Solution

``````1class Solution {
2    maxNiceDivisors(primeFactors) {
3        if (primeFactors <= 3) {
4            return primeFactors;
5        }
6
7        const kMod = 1000000007;
8        const pow3 = this.myPow(3, Math.floor(primeFactors / 3), kMod);
9
10        if (primeFactors % 3 === 0) {
11            return pow3 % kMod;
12        }
13        if (primeFactors % 3 === 1) {
14            return (4 * this.myPow(3, Math.floor((primeFactors - 4) / 3), kMod)) % kMod;
15        }
16        return (2 * this.myPow(3, Math.floor((primeFactors - 2) / 3), kMod)) % kMod;
17    }
18
19    myPow(x, n, kMod) {
20        if (n === 0) {
21            return 1;
22        }
23        if (n % 2 === 1) {
24            return (x * this.myPow(x, n - 1, kMod)) % kMod;
25        }
26        return this.myPow((x * x) % kMod, Math.floor(n / 2), kMod);
27    }
28}``````

### C# Solution

``````1public class Solution {
2    public int MaxNiceDivisors(int primeFactors) {
3        if (primeFactors <= 3)
4            return primeFactors;
5
6        int kMod = 1000000007;
7
8        if (primeFactors % 3 == 0)
9            return (int)(MyPow(3, primeFactors / 3, kMod) % kMod);
10        if (primeFactors % 3 == 1)
11            return (int)((4L * MyPow(3, (primeFactors - 4) / 3, kMod)) % kMod);
12        return (int)((2L * MyPow(3, (primeFactors - 2) / 3, kMod)) % kMod);
13    }
14
15    private long MyPow(long x, int n, int kMod) {
16        if (n == 0)
17            return 1;
18        if (n % 2 == 1)
19            return x * MyPow(x, n - 1, kMod) % kMod;
20        return MyPow((x * x) % kMod, n / 2, kMod);
21    }
22}``````

### Conclusion

In this article, we discussed an optimization problem of determining the optimal distribution of prime factors so that their count is at most `primeFactors` while maximizing the count of nice divisors. We elaborated on our strategy and went step by step through our approach to solve the problem.

The solutions provided above are in various programming languages such as C++, Python, Java, JavaScript, and C#.