Potential infinite loop detected

JavaScript
1

Tell us what’s happening:
I’m taking a code quiz. My code is working. I’m getting the correct answers. But i’m being warned of a Potential infinite loop detected

// 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

// What is the smallest positive number that is evenly divisible by all of the numbers from 1 to num?
Your code so far

function smallestMult(num) {
    let factorial = 1;
    for (let j = 1; j < num; j++) {
        factorial += factorial * j;
    }
   
    let gotIt = false;
    let lowestNumber;
    for (let k = num; k < factorial; k++) {
        for (let m =1; m<=num; m++) {
            if (k % m !== 0 ) {
                break;
            }
            
            if (m === num) gotIt=true;
        }

        if (gotIt) {
            lowestNumber = k;
            break;
        } 

    }
    return lowestNumber;

}

Your browser information:

User Agent is: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:73.0) Gecko/20100101 Firefox/73.0.

Challenge: Problem 5: Smallest multiple

Link to the challenge:
https://www.freecodecamp.org/learn/coding-interview-prep/project-euler/problem-5-smallest-multiple

2

Your loop will take a very long time to run. This is why you are getting the warning. I would look for ways to significantly reduce the number of values that you check.

For example, you are not calculating the factorial correctly and that in significantly increasing your upper bound.

Also, can you think of a way to use the fact that your result must be a multiple of num?

1 Like
3

Thanks!
I’m calculating the factorial properly and i’ve added some optimizations. Getting the correct results but to get the Potential infinite loop detected warning

smallestMult(20) returns 232792560


function rFact(num) {
    if (num === 0) {
        return 1;
    } else {
        return num * rFact(num - 1);
    }
}

function smallestMult(num) {
    let factorial = rFact(num);
    let gotIt = false;
    let lowestNumber;

    for (let isThisTheLowest = 2*num; isThisTheLowest < factorial; isThisTheLowest=isThisTheLowest+num) {
        
        if (isThisTheLowest % num === 0  &&  isThisTheLowest % 2 === 0) { //optimizations
            gotIt = false;
            for (let m = 3; m <= num; m++) { // no point in checking 1 or 2
                if (isThisTheLowest % m !== 0) { //stop checking
                    break;
                }
                if (m === num) gotIt = true; // if we get here, 'm's are factors and we have our lowest number
            }

            if (gotIt) {
                lowestNumber = isThisTheLowest;
                break;
            }
       }
    }
    return lowestNumber;

}
4

It looks like your code is relatively optimized and pretty close to as fast as you can make it with this looping strategy.

If you are still getting the warning, then I think it is time to bring out the big math guns.

I’d look on Wikipedia for

  1. Least Common Multiple
  2. Euclidean Algorithm

The Wikipedia articles have a formula for calculating the LCM of multiple numbers, calculating the LCM of two numbers if you know their GCD, and a fast way to find the GCD of two numbers. These three formulas are your ticket to a faster code.

5

i tested speed of execution using performance web api

I’m getting to 200-275 ms to execute smallestMult(20)

6

Hey @mconnor, you can save a little time by failing fast, i.e. starting from m = num and counting down to m == 3. This saves time because stuff that’s not divisible by 2 or 5 is also not divisible by 10, and so on.

I’m not entirely happy that people are running into problems because of the loop protection. If I can figure out how disable it for just the Project Euler challenges, I will.

1 Like
7

I set up a counter and it runs thru both loops my way - by counting up -
39,834,012 times. By counting down as you suggested, i’m getting 35,605,740 loops.

But still getting a Potential Infinte Loop warning on

for (let isThisTheLowest = 2*num; isThisTheLowest < factorial; isThisTheLowest=isThisTheLowest+num) {

8

i’m thinking the way to do this is to calculate a list of factorials first and then loop thru the array

1 Like
9

The cleanest and fastest way to do it is to ditch the loops altogether and use the math formulas on Wikipedia.

I’m fairly sure that a list of factorials will not help you, because you have lots of chances to over-multiply and miss the LCM without reducing to a prime factorization.