#1808

Hard

LeetCode Problem Workspace

Maximize Number of Nice Divisors

Solve Maximize Number of Nice Divisors by splitting primeFactors into mostly 3s and using fast modular exponentiation.

Problem Statement

You are given an integer primeFactors representing how many prime factors, counted with multiplicity, you may use to build some positive integer n. After choosing n, a divisor of n is called nice if it is divisible by every distinct prime that appears in n. Your task is to return the maximum possible number of nice divisors over all valid choices of n.

This is not a brute-force construction problem because primeFactors can be as large as 10^9. The real goal is to distribute the total prime-factor budget across exponents so the number of nice divisors is maximized, then return that maximum modulo 1000000007. For example, when primeFactors = 5, one valid choice gives 6 nice divisors, and no construction with at most five prime factors does better.

Examples

Example 1

Input: primeFactors = 5

Output: 6

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

Example details omitted.

Constraints

1 <= primeFactors <= 109

Solution Approach

Reduce nice divisors to a product of exponent counts

If n has prime factorization p1^a1 * p2^a2 * ... * pk^ak, then a nice divisor must include every distinct prime at least once. For each prime pi, the exponent in the divisor can be chosen from 1 through ai, giving ai choices. That means the number of nice divisors is a1 * a2 * ... * ak, while the total number of used prime factors is a1 + a2 + ... + ak = primeFactors. So the problem becomes: split primeFactors into positive integers whose product is as large as possible.

Use the integer-break rule: prefer 3s, avoid leftover 1

For maximizing a sum-fixed product, 3 is the best building block. Repeatedly taking 3s grows the product faster than keeping larger chunks together. The only bad ending is a remainder of 1, because 3 * 1 is worse than 2 * 2. So the optimal cases are: if primeFactors <= 3, return primeFactors directly; if primeFactors % 3 == 0, return 3^(primeFactors/3); if the remainder is 1, return 3^((primeFactors-4)/3) * 4; if the remainder is 2, return 3^((primeFactors-2)/3) * 2.

Compute powers with modular exponentiation

The exponent can be huge, so multiplying 3 repeatedly will time out and overflow. Use fast power with repeated squaring under modulo 1000000007. This keeps the time logarithmic in the exponent and handles the hard constraint cleanly. The recursion angle in this problem usually appears in the power function, although an iterative binary exponentiation version works the same way.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

After the math reduction, the work is dominated by modular exponentiation. Fast power runs in O(log primeFactors) time because it halves the exponent each step, and it uses O(log primeFactors) space with a recursive implementation or O(1) extra space if written iteratively. The common wrong path is treating this as search over factorizations, which is infeasible for primeFactors up to 10^9.

What Interviewers Usually Probe

They want you to notice that nice divisors count as a product of exponent sizes, not to enumerate divisors of n.
They expect the integer-break insight that mostly 3s maximize the product under a fixed sum.
They are checking whether you can combine number theory reasoning with safe modulo power for very large primeFactors.

Common Pitfalls or Variants

Common pitfalls

Returning 1 for primeFactors = 2 or 3 because of generic integer break logic, even though this problem allows using all factors directly and the answer should be 2 or 3.
Leaving a remainder 1 as 3 + 1, which loses value compared with converting it to 2 + 2.
Building n or trying candidate factorizations explicitly, which misses the reduction and cannot scale to 10^9.

Follow-up variants

Ask for the actual exponent partition instead of only the maximum count, which still ends in mostly 3s with a small tail adjustment.
Replace nice divisors with ordinary divisors, changing the count formula from a1 * a2 * ... * ak to (a1 + 1)(a2 + 1)... and altering the optimization target.
Force exactly k distinct primes in n, which adds another constraint to the exponent partition and changes the best split.

FAQ

What is the key insight in Maximize Number of Nice Divisors?

The key insight is that if n = p1^a1 * p2^a2 * ... * pk^ak, then the number of nice divisors is a1 * a2 * ... * ak, because each distinct prime must appear at least once in the divisor. That turns the problem into maximizing a product with a fixed sum of primeFactors.

Why do we break primeFactors into mostly 3s?

For integer partitions with maximum product, 3 is the most efficient chunk. Using as many 3s as possible gives the best result, except when you would leave a remainder of 1, in which case you replace 3 + 1 with 2 + 2.

Why is the answer for primeFactors = 5 equal to 6?

The best split is 3 + 2, whose product is 6. One construction is 2^3 * 5^2 = 200, and its nice divisors count is 3 * 2 = 6 because the exponent choices must include both distinct primes.

Do I need recursion for the Math plus Recursion pattern here?

Not for the partition logic. The recursion usually appears in fast modular exponentiation, where you compute powers by squaring and halving the exponent, but an iterative binary exponentiation version is equally good.

What are the exact edge cases for LeetCode 1808?

When primeFactors is 1, 2, or 3, the answer is primeFactors directly. For larger values, use the remainder cases: remainder 0 gives 3^k, remainder 1 gives 3^(k-1) * 4, and remainder 2 gives 3^k * 2, all modulo 1000000007.

terminal

Solution

Solution 1: Problem Transformation + Fast Power

We can factorize $n$ into prime factors, i.e., $n = a_1^{k_1} \times a_2^{k_2} \times\cdots \times a_m^{k_m}$, where $a_i$ is a prime factor and $k_i$ is the exponent of the prime factor $a_i$. Since the number of prime factors of $n$ does not exceed `primeFactors`, we have $k_1 + k_2 + \cdots + k_m \leq primeFactors$.

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

Continue Practicing

#1799 maximize score after n operations #1819 number of different subsequences gcds #1823 find the winner of the circular game