Execution timeout on a recursive function

Question

I am doing the Smallest possible sum Kata on CodeWars, which works fine for most arrays, but I get stuck when the algorithm is processing very large arrays:

Given an array X of positive integers, its elements are to be transformed by running the following operation on them as many times as required:
if X[i] > X[j] then X[i] = X[i] - X[j]
When no more transformations are possible, return its sum ("smallest possible sum").

For instance, the successive transformation of the elements of input X = [6, 9, 21] is detailed below:
X_1 = [6, 9, 12] # -> X_1[2] = X[2] - X[1] = 21 - 9
X_2 = [6, 9, 6]  # -> X_2[2] = X_1[2] - X_1[0] = 12 - 6
X_3 = [6, 3, 6]  # -> X_3[1] = X_2[1] - X_2[0] = 9 - 6
X_4 = [6, 3, 3]  # -> X_4[2] = X_3[2] - X_3[1] = 6 - 3
X_5 = [3, 3, 3]  # -> X_5[1] = X_4[0] - X_4[1] = 6 - 3
The returning output is the sum of the final transformation (here 9).

And here is my recursive solution:

const solution =(numbers) => {

    //1. find bigger and smallest number in the array, and keep the index of the biggest number
    let bigger = Math.max(...numbers)
    let smaller = Math.min(...numbers)
    let index = numbers.findIndex((n)=> n === bigger)

    //2. return the result if the result of the subtraction is positive or null
    if (smaller === bigger) {
        return numbers.reduce((a,c) => a + c)
    }

    //3.substract and replace
    numbers.splice(index, 1, bigger-smaller)

    return solution(numbers)
}

So I was wondering which operation in my solution is causing the time out; which is the most time consuming for the processor to loop through?

So? What's your question? "wich operation is the most time consumming" ask the debugger? — Jonas Wilms, Apr 22 '21 at 15:16
the tool you are looking for is a profiler , see https://stackoverflow.com/questions/855126/what-is-the-best-way-to-profile-javascript-execution — Leo, Apr 22 '21 at 15:22
Also to solve the Kata, the actual answer is probably "all of them". This can be solved in at least O(n log n), maybe even O(n) instead of O(n²) — Jonas Wilms, Apr 22 '21 at 15:25
Ask yourself: if you have, for example, 20 and 3 - what does it mean "subtract 3 from 20 as many times as possible"? What would be the result? With what mathematical operation can you achieve the same result in one go? — georg, Apr 22 '21 at 15:29
To optimize I would first sort the array, and whenver value is changed it is placed in sorted order. Cleary its a game of indices. Searching for max & min each time is not the optimal algorithm — Mulli, Apr 22 '21 at 15:29
@JonasWilms What is `n`, the number of integers in the array, or the magnitude of the integers? — Bergi, Apr 22 '21 at 16:03
@bergi the number of integers, or is the magnitude of relevance? — Jonas Wilms, Apr 22 '21 at 16:40
@JonasWilms In that case, it's definitely linear: `return numbers.reduce(gcd) * numbers.length`. But the complexity of the `gcd` algorithm depends on the number of bits of the two numbers - we can assume that to be constant of course, bounded by JS' max integer :-) — Bergi, Apr 22 '21 at 16:52
@bergi yeah, let's not use bigints ... I just made a quick estimation without actually writing a solution and had some uncertainty, so didn't want to claim this is O(n), though I safely can now :) — Jonas Wilms, Apr 22 '21 at 17:16

trincot · Accepted Answer · 2021-04-22T16:26:51.757

The good thing about your solution is that it recognises that when all values are the same (smaller === bigger), that the sum should be calculated and return.

However, it is not so good that you subtract the smallest from the largest to replace the largest value. You have an interest in making these values as small as possible, so this is like the worst choice you could make. Using any other pair for the subtraction would already be an improvement.

Also:

Having to scan the whole array with each recursive call, is time consuming. It makes your solution O(²).
findIndex is really (inefficient) overkill for what indexOf could do here.
If you have decided on the pair to use for subtraction, then why not consider what would happen if you subtracted as many times as possible? You could consider what this means in terms of division and remainder...
You can avoid the excessive stack usage by just replacing the recursive call with a loop (while (true))

For finding a better algorithm, think of what it means when the array ends up with only 2 in it. This must mean that there was no odd number in the original input. Similarly, if it were 3, then this means the input consisted only of numbers that divide by 3. If you go on like this, you'll notice that the value that remains in the array is a common devisor. With this insight you should be able to write a more efficient algorithm.

I think the term *common denominator* leads to the [wrong algorithm](https://en.wikipedia.org/wiki/Lowest_common_denominator). Try [*common divisor*](https://en.wikipedia.org/wiki/Greatest_common_divisor) instead :-) — Bergi, Apr 22 '21 at 16:07

score 1 · Answer 2 · answered Apr 23 '21 at 04:00

here is the correct way of doing it ! much much shorter and efficient !

          const gcd = (a, b) =>
          b ? gcd(b, a % b) : a;
          
          const solution = numbers =>
          numbers.length * numbers.reduce(gcd);

you were right the right way to go was not with the euclidian algorithm but with finding out the gcd with this method. thanks !!

Execution timeout on a recursive function

2 Answers2