Sums of Parts Python 3

user_14061528 0
Viewed 541

Let us consider this example (array written in general format):

ls = [0, 1, 3, 6, 10]

Its following parts:

ls = [0, 1, 3, 6, 10]
ls = [1, 3, 6, 10]
ls = [3, 6, 10]
ls = [6, 10]
ls = [10]
ls = []

The corresponding sums are (put together in a list): [20, 20, 19, 16, 10, 0]

The function parts_sums (or its variants in other languages) will take as parameter a list ls and return a list of the sums of its parts as defined above.

I have tried like this but is not executed in given Execution Time.How can I speed up this code:

def parts_sums(ls):
    sums=[]
    if len(ls)==0:
        return[0]
    else:
        while len(ls)!=0:
            sums.append(sum(ls))
            ls.pop(0)
        sums.append(0)
        return sums
python performance
4 Answers

Here's an iterative, O(n) solution.

def parts_sums(ls):
    sums = [0] * (len(ls) + 1)
    for i, e in enumerate(reversed(ls)):
        sums[len(ls) - i - 1] += sums[len(ls) - i] + e
    return sums
user_78716850 
def parts_sums(ls):
    if len(ls) == 0: return [0]
    ret = [sum(ls)]
    ret.extend(parts_sums(ls[1:]))
    return ret
user_140533450 
def fn(ls):
    if len(ls)==0:
        return [0]
    return [sum(ls[i:len(ls)]) for i in range(len(ls))]

###################################
print(1,fn([0, 1, 3, 6, 10]))
print(2,fn([]))

output will be like

1 [20, 20, 19, 16, 10]
2 [0]
user_109703430

Here I have to reverse list twice, perhaps it is 2*O(n), unless res[-1] does not add up to complexity even more:

xs = [0,1,3,6,10]

def summed(xs):
    res = [0]
    for x in reversed(xs):
        res.append(x+res[-1])
    return reversed(res)

This should perform better, O(n):

def summed2(xs):
    res = [0]
    for i, x in enumerate(reversed(xs)):
        res = [x+res[0]] + res
    return res

assert summed2(xs) == [20, 20, 19, 16, 10, 0]
user_17583630
Related