1808. Maximize Number of Nice Divisors LeetCode Solution

In this guide, you will get 1808. Maximize Number of Nice Divisors LeetCode Solution with the best time and space complexity. The solution to Maximize Number of Nice Divisors problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximize Number of Nice Divisors solution in C++
Maximize Number of Nice Divisors solution in Java
Maximize Number of Nice Divisors solution in Python
Additional Resources

1808. Maximize Number of Nice Divisors LeetCode Solution image

Problem Statement of Maximize Number of Nice Divisors

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.
The number of nice divisors of 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 <= 109

Complexity Analysis

Time Complexity: O(\log n)
Space Complexity: O(1)

1808. Maximize Number of Nice Divisors LeetCode Solution in C++

class Solution {
 public:
  int maxNiceDivisors(int primeFactors) {
    if (primeFactors <= 3)
      return primeFactors;
    if (primeFactors % 3 == 0)
      return modPow(3, primeFactors / 3) % kMod;
    if (primeFactors % 3 == 1)
      return 4L * modPow(3, (primeFactors - 4) / 3) % kMod;
    return 2L * modPow(3, (primeFactors - 2) / 3) % kMod;
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  long modPow(long x, long n) {
    if (n == 0)
      return 1;
    if (n % 2 == 1)
      return x * modPow(x % kMod, (n - 1)) % kMod;
    return modPow(x * x % kMod, (n / 2)) % kMod;
  }
};
/* code provided by PROGIEZ */

1808. Maximize Number of Nice Divisors LeetCode Solution in Java

class Solution {
  public int maxNiceDivisors(int primeFactors) {
    if (primeFactors <= 3)
      return primeFactors;
    if (primeFactors % 3 == 0)
      return (int) (modPow(3, primeFactors / 3) % kMod);
    if (primeFactors % 3 == 1)
      return (int) (4 * modPow(3, (primeFactors - 4) / 3) % kMod);
    return (int) (2 * modPow(3, (primeFactors - 2) / 3) % kMod);
  }

  private static final int kMod = 1_000_000_007;

  private long modPow(long x, long n) {
    if (n == 0)
      return 1;
    if (n % 2 == 1)
      return x * modPow(x, n - 1) % kMod;
    return modPow(x * x % kMod, n / 2);
  }
}
// code provided by PROGIEZ