Maximize Number of Nice Divisors — LeetCode 1808 Python Solution

The problem

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.

Example

Input

primeFactors = 5

Output

6

Explanation

200 is a valid value of n.

Python solution

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

Complexity

Pattern: Math and Number Theory

Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 1808. Maximize Number of Nice Divisors is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Math and Number Theory.

The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.

Related problems