Optimization in a time based algorithm

Question

I'm writing an algorithm for this problem, the algorithm is simple, I've already wrote the code but I can't see any possible optimization:

I have a bucket with 100 stones and 5 children that use it for decorate their sand castles. Every child pick up a stone repeatedly every a certain span of time, every child is independent from the others, more children can pick up a stone in the same time, there are 5 children in totals:

• Eric pick up a stone every 5 minutes
• Mark pick up a stone every 10 minutes
• Lara pick up a stone every 7 minutes
• Emma pick up a stone every 3 minutes
• Frank pick up a stone every 3 minutes

How many minutes exactly we need for empty the bucket?

To be more clear: after 10 minutes, Erick has up two stones (minute 5 and minute 10), while Emma has 3 stones (minute 3, 6 and 9).

So after 10 minutes the children have 2 + 1 + 1 + 3 + 3 = 10 stones in total, there are 90 stones in the bucket

This is my code (Python 3):

children_rate = [3, 3, 5, 7, 10]
bucket = 100

minutes = 0

while True:
    minutes += 1
    for child in children_rate:
        if minutes % child == 0:
            bucket -= 1
            if bucket == 0:
                print('bucket empty in',minutes,'minutes')
                exit()

This code works, in this case the minutes required are 91, but I can't use this code for process a bucket with 1 million of stones and 500 children.

The only optimization I can see is to transform the mod operation in a sum/add operation because division/multiplications are more expensive. I can use numpy arrays and so on but nothing that can really speed up the process.

I've tried to adapt the problem to some typical know problem described in my algorithm textbook without luck.

Answer 1

You can turn the algorithm around, so that for a given number of minutes you calculate how many stones have been used by all the children.

def compute_stones(minutes)
    stones = 0
    for child in children_rate:
        stones += minutes // child  # integer division
    return stones

Then you can do a binary chop to find the number of minutes at which stones = 100