1808. Maximize Number of Nice Divisors (Leetcode)

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 10⁹ + 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

Example: 2

Input: primeFactors = 8

Output: 18

Constraints:

• 1 <= primeFactors <= 10 ^ 9

Pre-requisite:

• To solve this problem we need to know a concept called Binary Exponentiation.

Key Observations #1:

• First thing we need to see is, if we select some K prime numbers to form our required N, then each of the K prime numbers must be included into our divisor, so that our divisor is a nice divisor.
• Let's say to make a number N, we have chosen 3 prime numbers A, B and C.
• So for a number N to be divided by all A, B and C at the same time (as the problem statement requires), all of them must be included in N.

Key Observations #2:

• Now let's see that we have selected a prime number, say A, and say that we have chosen it 3 times. Then we must include it at least once in the number N, that we will form.
• So we can add it 1 time, 2 times or 3 times, this gives us 3 ways of choosing it's occurence.
• Now we can see that we have to multiply the frequencies of all the unique prime numbers we have taken into consideration for forming N and we have to maximize the product of their counts.
• Now we can clearly see that the problem statement can be restated as : Breaking an Integer to get Maximum Product.
• Let's have a look at the first example to make it more clear. we have [2, 2, 2, 5, 5] and this gives us answer 6.
• We can see that 2 is taken 3 times and 5 is taken 2 times. So the result is multiplication of their frequencies (i.e 2 * 3 = 6).
• If you take the prime factor as [3, 3, 3, 5, 5], then also the answer will remain same, because we are not concerned by the value of prime factor, we are concerned only about their frequencies.

Moving on:

• Breaking an Integer to get Maximum Product is a standard problem.
• You can have the proof and solution here : GeeksForGeeks.

Full Code (Java): class Solution { int mod = 1000_000_000 + 7; public int maxNiceDivisors(int primeFactors) { if(primeFactors == 1) { return 1; } int q = primeFactors / 3; int r = primeFactors % 3; int f = 0; if(r == 1) { q--; f++; } // compute power of 3 ^ q long ans = compute(q) % mod; if(f == 1) { ans *= 4; ans %= mod; } if(r > 0) { ans *= r; ans %= mod; } return (int) ans; } // binary exponentiation long compute(int n) { if(n == 0) return 1; if(n == 1) return 3; long value = compute(n / 2); value = ((value % mod) * (value % mod)) % mod; if(n % 2 != 0) value *= 3; value %= mod; return value; } }