Summing all keys in the leaves of a tree My program takes 35 sec to run example 2. How can I make my program faster?

def sum_keys(K, inputs, count=1):
    A, B, M, L1, L2, L3, D, R = list(map(int, inputs))
    x = ((A*K)+B)%M
    y = ((A*K+2*B)%M)


    if K &lt; L1 or count == D:
        my_list.append(K)
    elif L1 &lt;= K &lt; L2:
        sum_keys(x, inputs, count + 1)
    elif L2 &lt;= K &lt; L3:
        sum_keys(y, inputs, count + 1)
    elif L3 &lt;= K:
        sum_keys(x, inputs, count + 1)
        sum_keys(y, inputs, count + 1)

    return sum(my_list)


def read_input(inputstring):
    inputs = inputstring.split()
    A, B, M, L1, L2, L3, D, R = list(map(int, inputs))
    x = ((A*R)+B)%M
    y = ((A*R+2*B)%M)

    if L1 &lt;= R &lt; L2:
        return sum_keys(x, inputs)
    elif L2 &lt;= R &lt; L3:
        return sum_keys(y, inputs)
    elif L3 &lt;= R:
        sum_keys(x, inputs)
        return sum_keys(y, inputs)

my_list = []
if __name__ == '__main__':
    print(read_input(input()))
return sum(my_list)



You don't need to calculate the sum every time.  Do it just when count is 1:

if count == 1:
    return sum(my_list)


You have a recursive function, but your function doesn't care what itself returns.  All it cares about is the side-effect: mylist.append(K).  Just changing that (without any other changes) made the second example take less than a second.  It would be best to return my_list and let whatever is calling the function decide if it wants the sum.

In two places you say:


A, B, M, L1, L2, L3, D, R = list(map(int, inputs))



You don't need to convert to a list just to iterate.  That is what A, B, M, ... = ... does.  Just use A, B, M, ... = map(int, inputs).  That prevents the unnecessary storage of the numbers in memory.



Enough about efficiency.  Let's talk about other things.

Your naming is not ideal.  How does someone looking at your program know what A, B, M, etc. are?  They are just letters.  To tell you the truth, I have no idea what this program is doing.  If you had more descriptive names, it would be easier for future readers (possibly including you) to read the code.  PEP 8, the Python style guide, recommends snake_case for normal variables.

It is better not to use global variables.  I would suggest passing my_list as an argument to sum_keys() instead of relying on the existence of a global variable.