Optimizing Sums of Parts function for Code Wars

Question

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.

Your algorithm works, but is too inefficient. Do you think you can find a cleverer way to solve this that doesn't involved repeatedly adding together the same elements? — Bergi, Dec 30 '21 at 19:21
I can't think about another any solution now, but I wan't to know why the solution cause an optimization error @Bergi — zenab, Dec 30 '21 at 19:33
https://stackoverflow.com/questions/8269916/what-is-sliding-window-algorithm-examples — Bergi, Dec 31 '21 at 00:24
Another approach:; `const partsSums = (ns) => [0, ...ns .reverse ()] .map (((c) => (n) => c += n) (0)) .reverse ()`. It might be cleaner to extract `const continualAdd = (c) => (n) => c += n` and rewrite as `const partsSums = (ns) => [0, ...ns .reverse()] .map (continualAdd (0)) .reverse ()` — Scott Sauyet, Jan 01 '22 at 21:14

trincot · Accepted Answer · 2021-12-30T20:51:47.027

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;    
}

Thanks so much, sir @trincot for your effort. now I understand it well — zenab, Jan 02 '22 at 12:08

Optimizing Sums of Parts function for Code Wars

1 Answers1