Please help. I’m getting WA in HIRINGWO, although I think that my approach is correct. Can you please help me identify as to what the error in my appraoch/code is :
Approach :
given, K tasks and X days, we have to find K different integers such that
-
LCM(A1, A2, … Ak) = X
-
A1 + A2 + … + Ak = minimum possible
Now my approach is as follows :
=> Lets say K = 180. Then, first step is to find the prime factorization of 180, which is : 2 * 2 * 3 * 3 * 5.
=> Because we want to find the values such that the LCM is X, thus we can’t have two integers out of any of the K integers that have HCF greater than 1. This means that HCF(Ai, Aj) = 1. ( This was stated in the editorial too.)
=> So to implement this what i did was i grouped the factors together, in the following way : (2 * 2) * (3 * 3) * 5. So 180 becomes (4 * 9 * 5) and then i put these values in a Priority Queue
=> lets say X = 3
Then this is our answer (4 + 9 + 5)
=> lets say X > 3
Then we add 1 that number of times (4 + 9 + 5 + 1 + 1 + 1 … )
=> lets say X < 3.
Then we poll the minimum 2 elements from the Priority Queue, and then multiply them to get the new number, and then put it back. We repeat this until the size of the pq becomes equal to our X value
So in this case, we have [4, 9, 5] in the priority queue, and if X = 2, then we will have [20, 9] in the priority queue after this step, because we replace 4 and 5 by (4*5)
and then answer = 20 + 9 = 29
Code : Code Link
Can you please tell me what the problem is!? Why am i getting WA. Is the approach correct?