Link can anyone help how to find the minimum n?
I guess you find the number of factors of n. Each factor is a member of two pairs or only one pair in the case of sqrt(n). Given the small number of k, you can do this by brute force. Factors of a number - Definition, How to find Factors, Examples
As you have a time limit of 1 sec and a limit of n being 50, can you try simply finding the number of divisors of each number till some limit(let’s say 10^6). This can be done in nlogn. Then, just check for the first time you encounter 2n-1 or 2n.
yes you are right . But how to find minimum “n” by trying out all possible prime set?
I think , for a given k, You need to find smallest possible x and y , where the no of factors of x is (2 * K - 1) and no of factors of y is (2 * K) . So , To get some smallest possible value with p no of factors. one way is to prime factorise p and give them to smallest primes. As trying all possibilities for some no p (<=2*k) will not give TLE.
Reason to consider both x and y , and why not only find smallest no with 2 * K factors (y) , if there is a perfect square with (2 * k - 1) factors (consider sample case itself - (2 * 2) and (1 * 4)).
For Eg:
If K - 37 , Values of 2 * K is 74 and 2 * K - 1 is 73.
So , for 74 try all possible combinations like
(2 * 37) - 2^36 * 3^1 (factors would be (36+1) * (1+1)).
(1 * 74) - 2^73 (1+73).
For 73 , all possible combinations would be
(1*73). - So 2^72 (as factors would be (1+72)).
Hope this helps.
Lol , u write same as stackoverflow code , we want how u write / check all possible combinations
A number N can be written as a*b where a and b are its factors. But only those a and b produce the required result N if they are symmetric about the center of list of factors.
For ex: The factors of 12 are 1, 2, 3, 4, 6, 12.
Only the pairs symmetric about the center ex (1.12) , (2,6) , (3,4) have the product equal to 12. Therefore in this case the number of ways would be 3.
For F number of factors the number of ways would be
F/2 if the number of factors are even and
(F+1)/2 if the number of factors are odd(as the middle one would be paired with itself)
So, you should create a while loop with a condition equal to True and increment natural number n by 1 at the end of the loop.
Inside the while loop a for should be defined to calculate the number of factors of the given natural number n.
Then calculate the number of ways K according to above rules.
After the for loop still inside the while put an if to check if K matches the value entered and if it does, apply break.
Now outside the while loop print the value of n which is the desired answer.
please can u share code 
Apologies, I thought we just need the number to be representable in 50 ways. I didn’t know that we need EXACTLY 50 ways.
1 Like
For a given k, you you need 2*k factors (assuming the resulting N is not square, I think it can be proved that it is never square) so you prime factorise 2K. eg k = 50, 100 = 5*5*2*2. A value of N is therefore 5*7*2^4*3^4 or 45,360. There are other values of N with 50 pairs, eg 100 = 4*25 so another value of N = is 2 to the power of 24 time 3 cubed or 452,984,832. It seems to be intuitive which will be smallest but you could brute force all sensible ones.
Hey, I thought the same. But seems like the question here is specifically seeking the number with exactly k ways, not atleast.
You have to find the smallest number with 2k or 2k-1 factors
now for any number x, we can write
x= p_1^{a_1}+p_2^{a_2}+...+p_n^{a_n}
hence for x count of factors c will be
c=(a_1+1)*(a_2+1)*...*(a_n+1)
thus we can say that it is optimal to choose the smallest prime factors p_1,p_2...p_n, and then recursively find a_1,a_2...a_n (for more details see this comment).
Since the number of factors is very small, a brute force would easily work
AC Code
Similar problems-
Codeforces
Project Euler
Yeah , my bad.
Anyway atmax the no of prime factors for a number less than 100 will be atmost 6
64 - 2 , 2 , 2 , 2 , 2 , 2.
So , possibilities for every prime factor to be in any of 6(atmost) groups. So complexity will be 6^6. we can do Backtracking for that.
how did you came up with that we have to find 2K or 2K-1 factors?
let a pair be (a,b) now a*b=n
(a,b) and (b,a) are the same
so we need exactly k distinct pairs
when can we get k pairs? when number of factors for any number is 2k or 2k-1
why 2k-1? consider n=4,
how many factors? 3
how many pairs? 2
2 Likes