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:
- The number of prime factors of n (not necessarily distinct) is at most
primeFactors
. - The number of nice divisors of
n
is maximized. A divisor ofn
is considered nice if it is divisible by every prime factor ofn
.
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
- If
primeFactors
is less than or equal to 3, returnprimeFactors
as no distribution of prime factors can create a higher number of nice divisors. - If
primeFactors
is divisible by 3, returnmyPow(3, primeFactors / 3) % kMod
because the optimal distribution of prime factors can be achieved using only 3's. - If
primeFactors % 3 == 1
, return4L * myPow(3, (primeFactors - 4) / 3) % kMod
because the optimal distribution can be achieved with one 2 and the rest being 3's. - If
primeFactors % 3 == 2
, return2L * 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#.