CODEWITHSUNDEEP
javascriptalgorithm
julBayonna
julBayonna

Reputation: 449

Execution timeout on a recursive function

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?

Upvotes: 0

Views: 194

Answers (2)

julBayonna
julBayonna

Reputation: 449

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 !!

Upvotes: 1

trincot
trincot

Reputation: 350715

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.

Upvotes: 1

Related Questions