Optimizing Sums of Parts function for Code Wars-CodePudding

I am looking at the Sums of Parts problem on CodeWars:

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.

The goal of the function is to sum elements of array then shift the first element of array each time until the length of array becomes 0.

I have this solution for it:

function partsSums(ls) {
    let len = ls.length;
    let arr = [];
    for (let i = 0; i < len  1; i  ) {
        arr.push(summation(ls));
        ls.shift();
    }

    function summation(a) {
        let sum = 0;
        for (let i = 0; i < a.length; i  ) {
            sum  = a[i];
        }
        return sum;
    }
    return arr;
}

It works when I run it in my editor: all test cases on CodeWars that successfully complete pass, but when I try to submit, I get this error:

Process was terminated. It took longer than 12000ms to complete

I'm new to algorithms and can't understand where the error is? Any suggestions are welcome.

CodePudding user response：

The goal of the function is to sum elements of array then shift the first element of array each time until the length of array become 0

The code challenge actually doesn't speak of shifting. You can do this without shifting, by storing the values immediately at the right index in the result array. Also, your function summation is summing some of the same values repeatedly. This can be avoided.

Take this example:

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

The output can be constructed as follows:

Create an array that is one element longer, and has the value 0 at the end:
```
ls:     0  1  3  6 10
result: .  .  .  .  .  0
```
(The values at the points are not relevant at this point)
Then start from the right side, and create a (backwards) running sum:
```
ls:     0  1  3  6 10
result: ↓  ↓  ↓  ↓  ↓← 0
        ↓  ↓  ↓  ↓←10
        ↓  ↓  ↓←16
        ↓  ↓←19
        ↓←20
       20
```
So the previous result at index i 1 is added to the input at index i, and so it works backwards to the start of the array.

Here is an implementation:

function partsSums(ls) {
    let result = Array(ls.length   1).fill(0);
    for (let i = ls.length - 1; i >= 0; i--) {
        result[i] = ls[i]   result[i   1];
    }
    return result;    
}