Lowest common multiple algorithm

Lowest common multiple algorithm
0

#1

Hi,
I can find the lowest common multiple but it’s inside a recursive function and when the recursive function steps out, the value of the lowest common multiple is not passed back to my main function. I can’t figure out out to pass the value out of the last function call and therefore have my result.

I’m sure that’s ambiguous. Here’s my code:


function smallestCommons(arr) {
  var theEnd=0;
  var fullArr=missingSequence(arr);
  //console.log(fullArr);
  var reversedArr=fullArr.reverse();
  //console.log("reversedArr=",reversedArr);
  var theEnd=whittle(reversedArr);
  console.log(theEnd);

}


smallestCommons([1,5]);
// thoughts:
//1.  will need to reduce an array by getting the product of all elements.
//2.  then will need to determine if that product is the lowest common multiple.
// 3.  An array of multiples for each number in the sequence will have to be created.
// 4.  From that, find the LCM by comparing each array to all other arrays.
function whittle(arr) {
  var lowCommon=1;
  var whittleArr=[];
  //var lCM=0;
  var count=0;
    for (i=0; i<arr.length-1; i++) {
      count=i;
      whittleArr[i]=leastCommonMult(arr[i], arr[i+1]);
    }
    console.log("whittleArr=",whittleArr);
    if (whittleArr.length!==1) {

      //theEnd=lCM;
      whittle(whittleArr);
    } else {
      console.log ("whittle 0", whittleArr[0]);
      var lCM=whittleArr[0];
      console.log("LCM", lCM);
      return lCM;
    //  lCM=whittleArr;
    //  console.log ("LCM=",lCM);
    }
    //  whittle(whittleArr);
    //}
//    console.log("LCM before final return=", whittleArr[0]);
    //return whittleArr;
}
function greatCommonDivisor(a, b) {
  var rem=1;
  var large=0;
  var small=0;
  if (a===0 || b===0) {
    alert("division by zero");
    console.log("division by zero");
    return;
  } else {
    rem=b % a;
  }
  if(rem>0) {
    small=rem;
    large=a;
    console.log("small=", small, "large=", large);
    greatCommonDivisor(small,large);
  }
  if (small !==0) {
    return small;
  } else {
    return a;
  }
}
function leastCommonMult(a,b) {
  var large=0;
  var small=0;
  if (a<b) {
    large=b;
    small=a;
  }else {
    large=a;
    small=b;
  }
  console.log("divisor = ", greatCommonDivisor(small,large));
  var lcm=(small/(greatCommonDivisor(small,large))) * large;
  return lcm;
}
function missingSequence(testArr) {
  var count=1;
  if(testArr[1]<testArr[0]) {
    testArr.reverse();
  }
  var diff= testArr[1]-testArr[0];
  //console.log(diff);
  while (diff-1>0) {
    //console.log(testArr[0] + count);
    //console.log(testArr);
    var newArr= testArr.splice(count,0,(testArr[0]+count));
    //console.log(testArr);
    diff -=1;
    count += 1;
  }
  return testArr;
}


thanks in advance.


#2

Hi @gobees,
Your code has some errors:

function smallestCommons(arr) {
  var theEnd=0; <-- here 
  ... 
  var theEnd=whittle(reversedArr); <-- here
}
    for (i=0; i<arr.length-1; i++) {    <-- the i is used but not declared
    
    }

With the help of http://www.vizit.tech/visualize I could identify the problem:
function whittle(arr) {

    if (whittleArr.length!==1) {
      whittle(whittleArr);  <-- here you need a "return"
    } else {
      var lCM=whittleArr[0];
      return lCM;
    }
}

Cheers and happy coding :slight_smile:


#3

thanks for identifying but that did not solve the stated problem


#4
  • Line 8 :

return theEnd;

  • Line 32:
return whittle(whittleArr);

Cheers and happy coding :slight_smile:


#5

Whew. That was a doozie. I can say I grunted all the way through it. Glad it’s done. Learned a lot.

I actually had a logic error in my GCD calculation that was working for LCM(1,5), LCM(5,1), LCM(1,13) but not LCM (23,18).

go figure…