You are given a positive integer primeFactors. You are asked to construct a positive integer n that satisfies the following conditions:
n (not necessarily distinct) is at most primeFactors.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 109 + 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 Explanation: 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
Constraints:
1 <= primeFactors <= 109Problem Overview: You are given an integer primeFactors, representing how many prime factors (with multiplicity) a number can contain. The task is to construct such a number so the count of nice divisors is maximized. A divisor is "nice" if it is divisible by every distinct prime factor of the number.
Approach 1: Integer Partition / Brute Mathematical Exploration (Exponential)
Start by modeling the number as n = p1^a1 * p2^a2 * ... * pk^ak where the sum of exponents equals primeFactors. The number of nice divisors becomes a1 * a2 * ... * ak. A brute strategy tries all possible partitions of primeFactors into exponent groups and computes the product for each partition. This reveals the mathematical pattern that smaller balanced parts maximize the product. The approach is mainly theoretical because enumerating partitions grows exponentially. Time complexity is exponential and space complexity is O(n) for recursion.
Approach 2: Greedy Factorization (Optimal) (O(log n) time, O(1) space)
The optimization reduces to maximizing the product of integers whose sum equals primeFactors. This is the classic integer break result: the product is maximized when the number is split into as many 3s as possible. If the remainder is 1, convert 3 + 1 into 2 + 2 to increase the product. That leads to three cases: if n % 3 == 0 use 3^(n/3), if n % 3 == 1 use 3^(n/3 - 1) * 4, and if n % 3 == 2 use 3^(n/3) * 2. Because results grow extremely large, compute powers using modular exponentiation under 1e9 + 7. The core operations are integer division, modular multiplication, and fast power.
The reasoning comes from math and number theory: splitting a number into equal parts maximizes product, and 3 provides the best multiplicative growth. Modular fast exponentiation can be implemented iteratively or using recursion with repeated squaring.
Recommended for interviews: The greedy factorization with fast modular exponentiation is the expected solution. Interviewers want to see the mathematical reduction from divisor counting to integer product maximization. Mentioning the partition insight first shows understanding, then implementing the O(log n) modular power solution demonstrates strong algorithmic thinking.
The task requires maximizing the number of nice divisors of n. To achieve this, we need to distribute the prime factors efficiently. When prime factors are distributed as powers, the number of divisors is maximized. The idea is similar to maximizing the product by dividing a number into parts such that the multiplication of parts is maximized, leveraging the properties of exponentiation.
Key Idea: Divide the factors into parts 3 and 2, as the number 3 contributes more efficiently to the product than smaller numbers, except when we have less than 3 factors where we prioritize 2.
This implementation optimizes the formation of n by maximizing the use of the factors. The use of pow optimally handles exponentiation with modulo operation effectively for large arguments due to the constraint size.
Time Complexity: O(log n) — due to the use of pow which uses exponentiation by squaring.
Space Complexity: O(1) — only a constant amount of additional space is used.
We can factorize n into prime factors, i.e., n = a_1^{k_1} times a_2^{k_2} timescdots 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.
According to the problem description, we know that a good factor of n must be divisible by all prime factors, which means that a good factor of n needs to include a_1 times a_2 times cdots times a_m as a factor. Then the number of good factors k= k_1 times k_2 times cdots times k_m, i.e., k is the product of k_1, k_2, cdots, k_m. To maximize the number of good factors, we need to split primeFactors into k_1, k_2, cdots, k_m to make k_1 times k_2 times cdots times k_m the largest. Therefore, the problem is transformed into: split the integer primeFactors into the product of several integers to maximize the product.
Next, we just need to discuss different cases.
primeFactors \lt 4, then directly return primeFactors.primeFactors is a multiple of 3, then we split primeFactors into multiples of 3, i.e., 3^{\frac{primeFactors}{3}}.primeFactors modulo 3 equals 1, then we split primeFactors into \frac{primeFactors}{3} - 1 multiples of 3, and then multiply by 4, i.e., 3^{\frac{primeFactors}{3} - 1} times 4.primeFactors modulo 3 equals 2, then we split primeFactors into \frac{primeFactors}{3} multiples of 3, and then multiply by 2, i.e., 3^{\frac{primeFactors}{3}} times 2.In the above process, we use fast power to calculate the modulus.
The time complexity is O(log n), and the space complexity is O(1).
Python
Java
C++
Go
JavaScript
| Approach | Complexity |
|---|---|
| Greedy Factorization Approach | Time Complexity: O(log n) — due to the use of |
| Problem Transformation + Fast Power | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Integer Partition Exploration | Exponential | O(n) | Useful only for deriving the mathematical pattern or understanding why equal partitions maximize product |
| Greedy Factorization with Modular Exponentiation | O(log n) | O(1) | Optimal approach for large constraints where direct multiplication would overflow |
| Recursive Fast Power Implementation | O(log n) | O(log n) | When implementing modular exponentiation using recursion instead of an iterative loop |
Leetcode 1808. Maximize Number of Nice Divisors • Fraz • 2,483 views views
Watch 7 more video solutions →Practice Maximize Number of Nice Divisors with our built-in code editor and test cases.
Practice on FleetCode