I was solving this problem and getting TLE (time limit exceeded). I was doing it using priorityqueue collection in java.I stored all the given egg hatching ability in priorityqueue and after that i took the first(smallest) element from priorityqueue and find its next day of laying an egg by the given relation i.e.
**Hen[i] lays it's first egg on D[i]th day.
Hen[i] lays it's second egg on 2*D[i]+1 th day.
Hen[i] lays it's thrid egg on 3*D[i]+3rd day.
Hen[i] lays it's fourth egg on 4*D[i]+6th day.
Hen[i] lays it's fifth egg on 5*D[i]+10th day.
and so on..**
and get it added to prirityqueue and removes that first(smallest) element.
For example suppose we are given 3 egg hatching abilities and we have to find minimum number of days to produce atleast 3(k=3) eggs....
so my solution involve k iterations each time taking smallest value and calculate its next egg laying day and again add it to priorityqueue after removing smallest element..
so let the inputs given in question be
n=3 k=3
values of n hatching abilities=1,2,3
for k=1
we just need 1 day.
for k=2
now i have calculated next egg laying day of first hen i.e.2*(1)+1=3 and remove 1 from priority queue and add 3 to it ,so now priority queue will look like 2,3,3
ans for k=2 is 2..
for k=3
again doing the same procedure and finding the next egg laying day of first hen in priority queue i.e 2*(2)+1=5..
and again removing 2 from queue and adding 5 to it now the queue will look like..3,3,5
hence answer for k=3 is 3..
In each case after k iterations answer is the smallest element in priorityqueue.
**so basically it iterates k times and left me with TLE **
Is there any approach independent of k or how could i improve it further..
Find an efficient way to obtain the number of eggs a single hen produces within $x$ days. Then make a binary search for the right number of days.