Maximize Number Of Nice Divisors - Leetcode Solution

Problem Statement:

You are given an integer n. You have to find the maximum number of nice divisors of any number in the range [1, n].

A number k is said to be a nice divisor of another number n if k is a divisor of n and k is not equal to 1.

Solution:

Approach:

• We have to maximize the number of nice divisors of any number in the range [1, n].
• We can use prime factorization to maximize the number of nice divisors.
• To maximize the number of nice divisors, we have to divide the number n into as many factors as possible.
• We can represent n as a product of its prime factors such that n = p1^a1 * p2^a2 * ... * pk^ak.
• Now we need to find the maximum number of nice divisors that can be formed using these prime factors.
• To maximize the number of nice divisors, we can choose the power ai of prime factor pi such that the product of all powers is closest to n.

Steps:

• Step 1: We find the prime factorization of n.
• Step 2: We then find the product of all powers of prime factors pi raised to the power ai, i.e. (p1^a1) * (p2^a2) * ... * (pk^ak).
• Step 3: If the product is greater than n then we can reduce the powers to form as many factors as possible. For example, if the product is 24 and n is 20 then we can reduce the power of 2 from 3 to 2. So the product becomes 16 which is less than 20 but has more factors than 24.
• Step 4: If the product is less than or equal to n then we can increase the powers to form as many factors as possible.

Algorithm:

• Initialize a variable maxDiv to 10^9 + 9.
• Iterate through the numbers i from 2 to sqrt(n).
• If n is divisible by i, then divide n by i and increase the count of its powers.
• If n is not divisible by i, move on to the next number.
• Calculate the product of all powers of the prime factors.
• If the product is greater than n then reduce the power of the prime factor with the largest power.
• If the product is less than or equal to n then increase the power of the prime factor with the smallest power.
• Return the product of all powers of the prime factors.

Code:

class Solution { public: int maxNiceDivisors(int n) { int mod = 1e9 + 7; if (n <= 3) return n; long long ans = 1; while (n > 4) { ans = (ans * 3) % mod; n -= 3; } return (ans * n) % mod; } };

Time Complexity:

The time complexity of the above algorithm is O(logn) as we iterate through the numbers from 2 to sqrt(n) and then reduce or increase the powers of prime factors as required.

1