Smallest Common Multiple - Overflow problem?

Smallest Common Multiple - Overflow problem?
0

#1

Tell us what’s happening:
Ok, so I know this code is far from an efficient means to the end for this problem but in theory it should work (and it does for all but the last case). However that last case is giving undefined behavior for the return result, returning seemingly random values. I’m assuming I’ve reached some sort of max iterations issue or something as repl.it does not let me run this either stating potential infinite loop.

My question is am I correct on this assumption? What is the constraint imposed by freecodecamp for iteration count? Is this code absolutely trash? :stuck_out_tongue_winking_eye:

Your code so far


function smallestCommons(arr) {
  if (arr[0] > arr[1]) {
    arr.reverse();
  }
  var i = arr[0];
  var j = arr[1];
  var prod = 1;
  
  console.log(arr);
  var btwn = [];
  for (let k=i; k<=j; k++) {
    btwn.push(k);
    prod*=k;
  }
  console.log(btwn,prod);

  for (let f=0; f<btwn.length; f++) {
      console.log(btwn[f]);
    }

  for (let d=1; d<=prod; d++) {
    for (let f=0; f<btwn.length; f++) {
      if (d % btwn[f] != 0) {
        d++;
        f=0;
      } 
    }
    console.log(d); 
    return d;
  }
  
}


smallestCommons([23,18]);

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/69.0.3497.100 Safari/537.36.

Link to the challenge:
https://learn.freecodecamp.org/javascript-algorithms-and-data-structures/intermediate-algorithm-scripting/smallest-common-multiple


#2

Your code is triggering the built in infinite loop protection, but even if it was not, your solution is incorrect for the last test case. Your solution will return 2018940 for the last test case. I would have to study your code more to give you more feedback as to why, but the bottom line is, your algorithm is incorrect.

One common approach is to understand that the smallest common multiple (smc) of any two numbers, is the product of the two numbers divided by their greatest common divisor (gcd). So how do you calculate the gcd of two numbers? Research the Euclidian algorithm for how to calculate the gcd of two numbers. It is a fairly straight forward algorithm.

Once you know how to calculate the scm of any two numbers, you would first calculate the smc of first two elements in the btwn array. Next, you would calculate the smc of the previous smc result and the third btwn element, and so on until all numbers in btwn have been used in an smc calculation. The final smc is the smc for all the numbers in the btwn array.

Hope this helps.


#3

Yeah I ended up switching to Euclid’s algorithm for my final solution since this wasn’t working. Don’t think it’s worth debugging this really inefficient alternative since we know Euclid’s will be exceptionally better.

function smallestCommons(arr) {
  if (arr[0] < arr[1]) {
    arr.reverse();
  }
  var i = arr[0];
  var j = arr[1];
  var prod = 1;
  
  console.log(arr);
  var btwn = [];
  for (let k=i; k>=j; k--) {
    btwn.push(k);
    prod*=k;
  }
  console.log(btwn,prod);

  for (let f=0; f<btwn.length; f++) {
      console.log(btwn[f]);
    }
  function gcd(x,y) {
    if (y == 0) {
      return x;
    } else {
      return gcd(y,x%y);
    }
  }
  var lcm = btwn[0];
  for (let f=0; f<btwn.length; f++){
    var GCD = gcd(lcm,btwn[f]);
    lcm = (lcm*btwn[f]) / GCD;
  }
  
  return lcm;
}


smallestCommons([23,18]);