Maximize Number of Nice Divisors: The Power of 3s

You are given a positive integer primeFactors. You need to construct a positive integer n such that the total number of prime factors of n (counting multiplicity) equals primeFactors, and the number of nice divisors of n is maximized. A nice divisor of n is a divisor that is divisible by every prime factor of n. Return the number of nice divisors modulo 10^9 + 7.

This is LeetCode 1808: Maximize Number of Nice Divisors.

Why this problem matters

At first glance, this problem looks like it involves number theory and divisor counting. But once you peel back the layers, it reduces to a classic optimization question: given a number, split it into parts that maximize the product. This same structure appears in "Integer Break" (LeetCode 343) and in various combinatorics problems. The math behind it is elegant, and once you internalize the pattern, you can solve an entire family of problems in seconds.

The key insight

The number of nice divisors equals the product of the exponents in the prime factorization of n. So the problem reduces to: partition primeFactors into positive integers whose product is maximized.

Why? If you choose n = p1^a1 * p2^a2 * ... * pk^ak, the total number of prime factors is a1 + a2 + ... + ak = primeFactors. A nice divisor must include at least one copy of every prime, so the count of nice divisors is (a1) * (a2) * ... * (ak). You want to maximize that product.

The optimal strategy: use as many 3s as possible.

• If primeFactors % 3 == 0: use all 3s. Answer = 3^(primeFactors/3)
• If primeFactors % 3 == 1: replace one 3 with two 2s (since 2*2 > 3*1). Answer = 3^((primeFactors-4)/3) * 4
• If primeFactors % 3 == 2: use one 2 and the rest 3s. Answer = 3^((primeFactors-2)/3) * 2

For large primeFactors, you need modular exponentiation (fast power) to compute the result without overflow.

The solution

def max_nice_divisors(prime_factors: int) -> int:
    MOD = 10 ** 9 + 7

    if prime_factors <= 3:
        return prime_factors

    remainder = prime_factors % 3

    if remainder == 0:
        return pow(3, prime_factors // 3, MOD)
    elif remainder == 1:
        return (pow(3, (prime_factors - 4) // 3, MOD) * 4) % MOD
    else:
        return (pow(3, (prime_factors - 2) // 3, MOD) * 2) % MOD

The three branches correspond to the three remainder cases when dividing primeFactors by 3.

When the remainder is 0, every part is a 3, so the answer is 3^(primeFactors/3).

When the remainder is 1, you would have a leftover 1 if you used all 3s. A part of size 1 contributes nothing to the product (multiplying by 1 is useless). Instead, remove one 3 and combine it with the leftover 1 to get 4. That gives you 3+1 = 4, and 2*2 = 4 > 3*1 = 3. So the answer is 3^((primeFactors-4)/3) * 4.

When the remainder is 2, just append a single 2 to the pile of 3s. The answer is 3^((primeFactors-2)/3) * 2.

Why is 3 optimal? You can show this with the AM-GM inequality or by direct comparison. For any part of size k >= 5, you can always decompose it into smaller parts with a larger product. For example, 6 = 3+3 and 3*3 = 9 > 6. Parts of size 4 are equivalent to 2+2 (product 4 either way). Parts of size 2 are fine, but three 2s give 2*2*2 = 8, while two 3s give 3*3 = 9 for the same sum of 6. So 3s always dominate.

Visual walkthrough

Here is the step-by-step reasoning behind the formula, showing why 3 is the magic number and how to handle each remainder case.

The key takeaway: the entire solution is just three lines of arithmetic plus a modular exponentiation call. The hard part is convincing yourself that the math is correct.

Complexity analysis

Time: O(log n) for the modular exponentiation. The rest is O(1) arithmetic.

Space: O(1). Only a few variables are needed.

The building blocks

1. Partition to maximize product

The core principle: when splitting n into parts to maximize the product, always prefer 3s over 2s. Never use parts of size 1 (they waste a slot) and never use parts larger than 4 (they can always be decomposed into 2s and 3s with a better product).

if n % 3 == 0:
    return 3 ** (n // 3)
elif n % 3 == 1:
    return 3 ** ((n - 4) // 3) * 4
else:
    return 3 ** ((n - 2) // 3) * 2

2. Modular exponentiation

When the exponent is enormous (up to around 10^9 / 3), you cannot compute the power directly. Modular exponentiation uses repeated squaring to compute base^exp mod m in O(log exp) time.

result = pow(base, exponent, modulus)

In languages without a built-in three-argument power function, you would implement this yourself with a loop that squares the base and reduces the exponent by half at each step.

Edge cases

• primeFactors = 1: only one prime factor, one exponent of 1, answer is 1
• primeFactors = 2: split as just 2, answer is 2
• primeFactors = 3: one part of 3, answer is 3
• primeFactors = 4: 2+2 = 4 (not 3+1), answer is 4
• Very large primeFactors: modular exponentiation handles values up to 10^9 without issue

From understanding to recall

The "use 3s" insight feels like a magic trick the first time you encounter it. But it follows from a clean mathematical argument: among all positive integers, 3 maximizes the ratio of ln(k)/k, which means splitting into 3s grows the product fastest per unit of sum consumed. The three remainder cases and the modular exponentiation are compact enough to memorize, and spaced repetition locks them in so you never have to re-derive the formula under time pressure.

Related posts

• Climbing Stairs - A simpler dynamic programming problem that shares the idea of optimal substructure
• Power of Three - Working with powers of 3 and mathematical properties
• Pow(x, n) - The fast exponentiation technique used here for modular arithmetic

Once you have the partition-to-maximize-product pattern in your toolkit, a whole class of math problems becomes routine. CodeBricks helps you build that toolkit through targeted practice and spaced review, so the patterns stay sharp when you need them most.