Solution going too slow

JavaScript
1

Tell us what’s happening:
I understand, that a nested for loop is not going to work, But I still do not understand how to do it the other way. Thanks in advance for letting me know.

Your code so far


function findDivisors(number) {
let resultArray = [];
for (let i = 1; i < number; ++i) {
  if (number % i === 0) {
    resultArray.push(i);
  }
}
return resultArray;
}

function CheckIfAmicablePair(number1, number2) {
return findDivisors(number1).reduce((acc, curr) => acc + curr) === number2 && findDivisors(number2).reduce((acc, curr) => acc + curr) === number1
}

function amicablePairsUpTo(maxNum) {
let arrayResult = [];
for (let i = 2; i < maxNum; ++i) {
  for (let j = 2; j < maxNum; ++j) {
    if (i != j && CheckIfAmicablePair(i, j)) {
      arrayResult.push([i, j]);
    }
  }
}
return arrayResult;
}

console.log(amicablePairsUpTo(20000))

Your browser information:

User Agent is: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/86.0.4240.183 Safari/537.36.

Challenge: Amicable pairs

Link to the challenge:

2

Firstly, you don’t need an array of divisors if all you going to do is sum the values. Do it already in the for loop and return a number.

Regarding the loop - yes it won’t cut it. One technique would be to calculate the sum of divisors for each number and save them (say in an object) and then go over the keys in the object and check if the object has pairs of key: value that are inverse:

object = {
  ...
  220: 284,
  ...
  284: 220,
  ...
}

This way you’ll reduce complexity from O(n^2) to O(n) (I guess :thinking:)

3

I just tried the challenge myself and I solved it with a nested for loop, but I’m using it to build an object, where the key is the current number i (other loop), and the value is the sum of all divisors of that number (I think that’s also what jenovs suggested).

My code is quite slow though, too (takes about 6 seconds to complete), but it doesn’t time out.