Last Updated: 18 Apr, 2021
Maximize The Nice Divisor
Moderate
Asked in company
There is a fight between Spiderman and the Zombie. Spiderman has to protect the planet earth, and for this, he has to give punches in the head of the zombie. The Spiderman is given an integer ‘N’ and he has to construct a number ‘Num’ such that the count of nice divisors of ‘NUM’ is maximum and the constructed number has at most 'N' prime factors. It is not necessary for all prime factors of ‘NUM’ to be distinct. A divisor of ‘NUM’ is called nice if it is divisible by every prime factor of ‘NUM’. Assuming yourselves as spiderman protect the planet earth by returning the nice divisors of ‘NUM’.
Return the number of nice divisors of ‘NUM’. Since that number can be too large, return it modulo 10^9 + 7.
For Example:
If N = 12, then its prime factors are [2, 2, 3], then 6 and 12 are nice divisors, while 3, 4, and 2 are not.
Input format:
The first line of input contains an integer ‘T’, denoting the number of test cases.
The first line of each test case contains an integer ‘N’, denoting the count of prime factors that Spiderman has.
Output format:
For each test case, return the count of nice divisors of 'NUM' that will be constructed.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 1000
1 <= N <= 10^9
Time Limit: 1 sec
Approaches
Approach:
- This approach aims to break 'N' as a sum of 3’s repeatedly till it 'N' is greater than 4.
- Since every number 'NUM' can be represented in the form of prime factors, i.e., 'N' = A^K1 * B^K2 * C^K3 ... . Here the total number of its prime factors should be equal to 'N' = K1 + K2 + K3 … and the total number of nice divisors will be equal to K1 * K2 * K3… .
- 'N'ow we have to split 'N' into groups of 3 where groups refer to the frequency that each prime factor should have in our number 'NUM'. But we do not have to calculate the frequency of each prime factor separately so we split 'N' as a sum of 3’s.
- Let’s say we break 'N' into groups of 3 (XXXYYY…..), where X + X + X + Y + Y+ … = 'N' so the total number of nice divisors will be 3*3*3…. = P, but if we break 'N' into any random configuration (XXYYZZZZ …. ), and if we multiply A(Frequency of X), B(Frequency of Y), and so on then the total number of divisors will be less than P.
- You can verify the above statement by taking any value of 'N' which is greater than 4.
- Therefore we concluded that we will always divide 'N' into groups of 3 first and then in groups of 2 and 1 because it will give us the best result compared to dividing 'N' into any other configuration.
- If 'N' is less than or equal to 4, then the answer will be 'N' itself because, for 'N' equal to 1 and 2, we cannot split into groups of 3, and for 'N' equal to 3 and 4, splitting them into groups of 3 will give us less product. So this serves as the base case that if 'N' is less than or equal to 4, then we will return 'N' only.
- Therefore we will repeatedly subtract 3 from 'N' till 'N' is greater than 4. We will also keep variable 'RES' initialized to 1 and multiplying it with 3 again and again till 'N' is greater than 4 which will eventually lead to our answer.
Algorithm:
- First, check if 'N' is less than or equal to 4, then we will return 'N'.
- Create a variable 'RES' intialised to 1 which denotes our nice divisors.
- Then till the 'N' is greater than 4, perform the following steps:
- Multiply 'RES' with 3. Also, update 'RES' as ('RES' mod 10^9+7)
- Then decrement 'N' by 3.
- Then again, multiply 'RES' and 'N'. Also, update 'RES' as ('RES' mod 10^9+7).
- Finally, return 'RES'.
Approach:
- The idea behind this approach is that every number 'NUM' can be represented in the form of prime factors, i.e., A^K1 * B^K2 * C^K3 ... . and the total number of its prime factors should be equal to 'N' = K1 + K2 + K3 … . So the total number of nice divisors will be equal to K1 * K2 * K3… . It is because we can select prime factor ‘A’ through ‘K1’ options, prime factor ‘B’ through ‘K2’ options, and so on.
- So we do not have to actually calculate the prime factors, but instead, we have to find such configuration to break 'N' in K1, K2 … such that 'N' = K1 + K2 + K3 … . and product of K1 * K2 * K3… is maximized because its product is giving us the nice divisors.
- So basically we have to maximize the product of K1 * K2 * K3 …. And for this, if we break 'N' into ('N'/X) X’s equal parts, then their product is equal to X^('N'/X). 'N'ow, if we find the derivative of X^('N'/X) with respect to X and make it equal to 0 for maxima since we have to maximize the product, we will find that the value of ‘X’ is equal to ‘e’(base of natural logarithm) e = 2.718. This point is maxima because we have broken 'N' into equal parts. So the conclusion is that we have to break 'N' into groups of either 3 or 2.
- So we will keep breaking 'N' into groups of 3 because for every triplet of 2 we can replace it with a tuple of 3 to obtain the maximum product until the 'N' remains as 2 or 4.
- Finally, if 'N' is divisible by 3, then the answer will be 3^('N'/3).
- If 'N' on division by 3 leaves a remainder 1, then the answer will 3^('N'/3 - 1)*4. This is because we will split 'N' as a sum of 3’s and one 4. For example, if we take 'N' = 10 then we can break it into 3 + 3 + 4.
- If 'N' on division by 3 leaves a remainder 2, then the answer will be 3^('N'/3)*2. This is because we will split 'N' as a sum of 3’s and one 2. For example, if we take 'N' = 11 then we can break it into 3 + 3 + 3 + 2.
- The power of 3 can be calculated with the help of modular binary exponentiation.
Algorithm:
- First, check if 'N' is equal to 1, then return 1.
- Create a variable 'COUNT' initialized to 0 to count the number of nice divisors.
- If 'N' is divisible by 3, set 'COUNT' equal to Power(3, 'N'/3)%(10^9 + 7).
- If 'N' on dividing by 3 leaves a remainder 1, then set 'COUNT' equal to 4*Power(3, 'N'/3 - 1)%(10^9 + 7).
- Otherwise, set 'COUNT' equal to 2*Power(3, 'N'/3)%(10^9 + 7).
- Finally, return the 'COUNT'.
- Here ‘POWER’(X, Y) is a function that calculates the power of ‘X’ raised to ‘Y’.