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