Problem:
There are \$n\$ pigeons and \$m\$ grains. Pigeon \$i\$ eats a single grain every \$x_i\$ seconds. Find the time until all the grain is eaten.
Input:
A line with the integer \$m\$ giving the number of grains, followed by a line with \$n\$ integers \$x_1, x_2, \ldots, x_n\$ giving the time taken by each pigeon to eat one grain.
Currently I am doing a loop over each second and finding how many grains in that seconds are eaten. This with numpy I am able to get a good performance but for large inputs (\$m=10^{25}\$ and \$n=300000\$) the program runs forever.
What can I do mathematically to solve this?
import numpy
def melt(grains,birdTimes):
counter=0
counts = numpy.zeros(len(birdTimes,),dtype=numpy.int)
birdTimes = numpy.array(birdTimes)
while (grains>0):
counts=counts+1
temp=birdTimes-counts
zeroA = numpy.where(temp==0)[0]
grains = grains - len(zeroA)
counts[zeroA] =0
counter+=1
return counter
x
value for each bird. \$\endgroup\$