Maximize The Nice Divisor

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
2 upvotes
Asked in company
TCS

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5
4
Sample Output 1:
6
4
Explanation 1:
For the first test case, If we take ‘Num’ equal to 72, then its prime factors are [2, 2, 2, 3, 3], and the divisors of 72 are [1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72]. Among all the divisors, the nice divisors are [6, 12, 18, 24, 36, 72]. So the output is 6.

For the second test case, If we take ‘Num’ equal to 36, then its prime factors are [2, 2, 3, 3], and the divisors of 36 are [1, 2, 3, 4, 6, 9, 12, 18, 36]. Among all the divisors, the nice divisors are [6, 12, 18, 36]. So the output is 4.
Sample Input 2:
2
8
7
Sample Output 2:
 18
 12
Hint

Try to break the N as a sum of 3’s.

Approaches (2)
Observation Based

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'.
Time Complexity

O(N), where ‘N’ is the total number of prime factors.

 

Since for each N, we are breaking it into groups of 3 and then calculating the Res for each part of N, which takes O(N) time. So overall, time complexity will be O(N). 

Space Complexity

O(1).

 

Since constant space is being used. So overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Maximize The Nice Divisor
Full screen
Console