Maximize Number of Nice Divisors - Problem

You are given a positive integer primeFactors. You need 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: 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], so 6 and 12 are nice divisors, while 3 and 4 are not.

Return the number of nice divisors of n. Since the answer can be very large, return it modulo 109 + 7.

Input & Output

Example 1 — Basic Case
$ Input: primeFactors = 5
Output: 6
💡 Note: Optimal partition is [3,2] giving us nice divisors = 3 × 2 = 6. The number could be 2³×3² with nice divisors being multiples of 2×3=6.
Example 2 — All 3s
$ Input: primeFactors = 8
Output: 18
💡 Note: 8 % 3 = 2, so we use [3,3,2] partition. Nice divisors = 3 × 3 × 2 = 18.
Example 3 — Small Input
$ Input: primeFactors = 4
Output: 4
💡 Note: For small inputs ≤ 4, the answer is the number itself. Partition [4] or [2,2] both give 4.

Constraints

  • 1 ≤ primeFactors ≤ 109

Visualization

Tap to expand
Maximize Nice Divisors: primeFactors = 5Input: 5 prime factors5Try Different Partitions:[5]: 5[4,1]: 4[3,2]: 6Optimal: Use 3 and 2 to maximize productNice divisors = 3 × 2 = 66Output: Maximum nice divisors
Understanding the Visualization
1
Input
Given primeFactors = 5 (total count of prime factors)
2
Find Optimal Partition
Partition into groups that maximize product: [3,2]
3
Calculate Nice Divisors
Nice divisors = 3 × 2 = 6
Key Takeaway
🎯 Key Insight: Use mathematical optimization with mostly 3s to maximize the product of partition elements
Asked in
Google 15 Facebook 12 Microsoft 8
23.4K Views
Medium Frequency
~35 min Avg. Time
567 Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen