Algorithm Challenge (SmallestCommonMultiple): Can someone evaluate this?

JavaScript
1

Continuing the discussion from freeCodeCamp Challenge Guide: Smallest Common Multiple:

I came to this solution doing the exercise, and even though it works, the console warns me of potential infinite loops and for large numbers I believe it is not very efficient because of the nested loop.
Could you correct this code or tell me how could I improve it?
After watching many guides I don’t get a hang of the reduce function.

function smallestCommons(arr) {
  // Set smallest as start
  let [starter, last] = arr.sort((a,b) => a - b);
  let current = 1;
  for (let i = starter; i <= last; i++) {
    for (let j = 1; j != 0; j++) {
      // evaluate multiples of Starter vs Current
      if ((i * j) % current === 0) {
        // When found evaluate next number in Range
        current = i * j;
        break;
      }      
    }
  }
  return current;
}
console.log(smallestCommons([2,10])); // Result 2520
console.log(smallestCommons([23,18])); // Result 6056820

PS: “current” variable can be completely replaced by starter, I just changed it for readability.

function smallestCommons(arr) {
  // Set smallest as start
  let [starter, last] = arr.sort((a,b) => a - b);
  for (let i = starter; i <= last; i++) {
    for (let j = 1; j != 0; j++) {
      // evaluate multiples of Starter vs Current
      if ((i * j) % starter === 0) {
        // When found evaluate next number in Range
        starter = i * j;
        break;
      }         
    }
  }
  return starter;
}
console.log(smallestCommons([2,10])); // Result 2520
console.log(smallestCommons([23,18])); // Result 6056820
2

Can you explain what this code does? I can read the literal code and I know literally what it does, but I don’t know the process you are trying to model with the code.

3

Yes Jeremy, this is the first time I show any code to someone else, thank you for understanding.

What I did here is to get every lowest multiple compared to next number in range
Example input range[1,6]
lowestMultiple = 1, then we check number 1.
(1 * 1) % 1 = 0 so we check next (2)
lowestMultiple = 1, we check number 2
(2 * 1) % 1 = 0 so 2 becomes the lowest and we check next (3)
lowestMultiple = 2, we check number 3
(3 * 1) % 2 != 0, this multiplier does not work so we go to next
(3 * 2) % 2 = 0, this one does so now 3*2 is the lowest
lowestMultiple = 6, we check number 4,
4, 8, 12 is the first divisible by 6
12 becomes our new smallest and iterate to number 5
5,10,15,20,25,30 etc until 60 is the first divisible by 5
60 becomes our new smallest
and 60 is divisible by 6 too so [1,6] gives us a result of 60

By writing this I realized it could be achieved by multiplying the current one
so it is 6, 12 and then
12,24,36,48,60. to calculate bigger number is better this way, tried it and now works in enormous numbers.

Old version more comments

function smallestCommons(arr) {
  // Set smallest as start
    // This arranges the input and select the lowest number
    // as the starting point 
  let [starter, last] = arr.sort((a,b) => a - b);

   // This variable is the smallest common multiple currently
   // (for every independent number 1 is the smallest)
   // This can also be achieved in this exercise by 
   // the smallest number in the input
  let current = 1;
  // This iterates through the range of the given input values
  for (let i = starter; i <= last; i++) {
    // This iterates every positive number / multiple of a number
    // "j" becomes a multiplier  incrementing endlessly
    // Until a new lowest is found
    for (let j = 1; j != 0; j++) {
      // evaluate multiples of Starter vs Current
      // 
      if ((i * j) % current === 0) {
        // When found evaluate next number in Range
        current = i * j;
        break;
      }      
    }
  }
  return current;
}

Updated version


function smallestCommons(arr) {
  let [minimum, last] = arr.sort((a,b) => a - b);
  for (let i = minimum; i <= last; i++) {
    for (let j = 1; j != 0; j++) {
      if ((minimum * j) % i === 0) {
        minimum *= j;
        break;
      }      
    }
  }
  return minimum;
}

console.log(smallestCommons([100,24])) // result: 2.313176847909655e+107

Tell me what you think and thanks again Jeremy

4

I think you have some right pieces here, but your overall logic isn’t quite going to work. You are blending together the logic for checking if a number is a multiple and the logic for updating your current/minimum. I would split these apart.

I’d start with logic to check if a number is the multiple of every value from minimum to last. Then you can separately add the logic to update the current if the number is not a multiple.

5

I’ve been busting my head with this these days, but I don’t understand how to separate them.
I ended up with this improved version which just to be clear, until ranges 1,198 works a better than the first 2 given solutions by fCC.
Higher than that it results in strange behavior.
I understand that separating the functions would be better for functional programming, but I just haven’t been able to do it yet.

Thanks again for your time Jeremy

function smallestCommonsTwo(arr) {
  // Init
  const [min, max] = arr.sort((a, b) => a - b);
  // Highest Assured Value
  let current = max * (max - 1);
  // Loop every value
  for (let i = min; i <= max; i++) {
  // Check multiple from start to end of range
    if (current % i !== 0) {
      for (let j = 1; j !== 0; j++) {
  // Multiply current(MinMultiple) to get next current
        if ((current * j) % i === 0) {
  // Update current
          current *= j;
  // Stop multiplying and check next value from range
          break;
        }
      }
    }
  }
  return current;
}
console.log(smallestCommonsTwo([1,5])) // 60
console.log(smallestCommonsTwo([23,18])) // 6056820
console.log(smallestCommonsTwo([1,198])) // 1.5417184966767015e+306
console.log(smallestCommonsTwo([1,199])) /* Potential infinite loop detected on line 29. 
Tests may fail if this is not changed.
Potential infinite loop detected on line 26. 
Tests may fail if this is not changed.
9.0270569058967e+307 */

Ps: Should I stop using loops altogether, and use a method like every with reduce/filter?

6

Your loops are basically backwards of each other, which is why they are hard to detangle.

You are doing way too much multiplication, which is why I suggested that you start with a smaller task.

If you have a way to check if a number is a multiple of every number in a range without changing it, then you can wrap that is a loop that changes the number you are checking.

Trying to modify the ‘current’ based upon which number didn’t divide in evenly isn’t going to work. That approach isn’t mathematically sound.

7

I logged the multipliers to check how many millions operations were made, oops.

I was being stubborn on this one, just because it worked in smaller numbers I thought it would keep working.

Here we go, but it is not efficient, for large numbers it doesn’t work even though the math is right, or is it not??

function smallestCommonsTwo(arr) {
  // Init
  let [low, high] = arr.sort((a, b) => a - b);
  const range = Array.from({length: high - low + 1}, (_, i) => low + i);
  let multiplier = 2;
  // Highest Assured Value
  let currentMax = high;
  // Check every multiple of Highest
  while (!range.every(i => currentMax % i === 0)) {
    currentMax = high * multiplier;
    multiplier++;
  }
  return (currentMax);
}

Realizing the inefficiency of the previous code, I ended up using the Euclidean algorithm suggested in the answers, but differing from when I first looked at it, now understand how and most importantly WHY to use it. Thank you very much Jeremy.

function smallestCommons(arr) {
  // Init
  let [low, high] = arr.sort((a, b) => a - b);
  const range = Array.from({length: high - low + 1}, (_, i) => low + i);
  // Euclidean algorithm
  const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));
  const lcm = (a, b) => (a * b) / gcd(a, b);

  return range.reduce(lcm);
}

console.log(smallestCommons([1,200]))
8

The hard thing is that the math isn’t quite right, but it doesn’t show its flaws until you get big enough numbers, which makes it hard to trace.

I definitely like the Euclidean approach, though that’s because I learned math before programming :slight_smile: Nice work getting it passing

1 Like