[Solved] Basic While Loop (or logic?) Mistake

[Solved] Basic While Loop (or logic?) Mistake
0.0 0

#1

Working on the Intermediate Algorithm Scripting, on the Smallest Common Multiple. I’ve got the LCM function working and I understand the math, I don’t think that’s the issue. I’ve gotten the problem solved, down to creating an array full of initial LCMs. My next task is to combine the array full of LCMs into each other… essentially, LCM( LCM( LCM([0],[1]) ,[2]), [3]) .

The for(var k=0… portion inside the while loop seems to work fine, it takes each pair of numbers and applies the LCM function, and then removes the 2nd number. When troubleshooting, if I comment out the while loop, do the for(var=k… loop, and console.log the arrayOfLCM, the array is valid, they’re all LCMs (checked via online LCM calculator). The problem comes when I add in the while loop to keep going until the array is combined down to 1 value.

I get an answer, but it’s off by varying factors. [1,5] returns 720, twelve times the real answer (60)… [1,13] returns 720720, double the real answer (360360)… BUT [23,18] returns the CORRECT result of 6056820.

I know this has got to be in the while loop, if I get rid of the while loop and just return the arrayOfLCM after one iteration of the for(var k=0… loop, and check the values of all of said array’s elements using an online LCM calculator, it still returns correct.

(and yes, I’ve looked all over the forum, StackOverflow, etc… I understand the other solutions, but I don’t want to just copy those… I would like to know what idiocy is stopping me from making my original thought process work!)

smallestCommons([1,13]);

function smallestCommons(arr) {
  var inputArray = arguments[0];
  var lowerBoundary = Math.min.apply(Math, inputArray);
  var upperBoundary = Math.max.apply(Math, inputArray);
  var difference = upperBoundary - lowerBoundary;
  var arrayOfNumbersBetweenBoundaries = [];
  
  for (var i=0; i<=difference; i++) {
    arrayOfNumbersBetweenBoundaries.push(lowerBoundary + i);
  } //successfully creates array of numbers between the boundaries, [1,5] will return [1, 2, 3, 4, 5] etc...
  
  var arrayOfLCM = [];
  for (var j=0; j<arrayOfNumbersBetweenBoundaries.length-1; j+=1) {
    arrayOfLCM[j] = LCM(arrayOfNumbersBetweenBoundaries[j], arrayOfNumbersBetweenBoundaries[j+1]);
  }  //sucessfully creates array of least common multiples from the arrayOfNumbersBetweenBoundaries

  //now let's do a FOR loop to go through the array full of LCMs and apply function LCM() to each pair of numbers.
  //this will be the loop beginning with for(var k=0...
  //assign the new LCM to the first value, the [k], and then delete the 2nd value [k+1]
  //the loop will then move onto the next value (originally the 3rd value in the array, [2], now in the second [1] position)
  //and apply the LCM to that value, and the next value.... replacing the first value with answer, deleting the 2nd...
  //this essentially cuts the length of the array in half
  
  //Put all this in a WHILE loop, so it keeps running until we've combined the array down to one value
  while (arrayOfLCM.length>1) {
    for (var k=0; k<arrayOfLCM.length-1; k+=1) {
      arrayOfLCM[k] = LCM(arrayOfLCM[k], arrayOfLCM[k+1]);
      arrayOfLCM.splice(k+1,1);
    }
  }

  
  return arrayOfLCM[0];
}



function LCM(firstNum, secondNum) {
  var smallerNum = Math.min(firstNum, secondNum);
  var biggerNum = Math.max(firstNum, secondNum);
  var dividend = biggerNum;  //yes, I realize I could combine lines here, but leaving them separate helps me
  var divisor = smallerNum;  //keep track of which is which.
  var remainder = 1;
  var lastRemainder = 0;
  
  while (remainder > 0) {
    lastRemainder = remainder;
    remainder = dividend % divisor;
    dividend = divisor;
    divisor = remainder;
  }
  
  return smallerNum * biggerNum / lastRemainder;
}

#2

I didn’t have time to dive too deep into your code, but one thing jumped out at me in the [1,5] test. Your solution gives the LCM of 12 and 60 to be 720 when 60 is in fact a multiple of 12. Since the [1,5] test is going to include this step, you’re going to have at least one incorrect number in your array. I just added some comments to your code to track the state of the array.


#3

Hi jwuestef,

my method was a bit simpler:
I formed an array of all the numbers between the two given numbers.
I then took the highest number and multipled it (using a while loop) by 1,2,3 etc …in turn until the following condition was met : I checked if each number in the array divided into the current multiple without a remainder … if this condition was met then I exited the while loop … and the current multiple of was the required answer.

so for instance if the two number given were [ 5, 8]
I’d form an array =[5,6,7,8]
then mulitply 8 by one ,
then check if the other numbers in the array divided into that without a remainder , if not
then I’d mulitply 8 by 2
then check if the other numbers in the array divided into that without a remainder , if not
and so on until all numbers in the array divided the current multiple of 8 without a remainder and that would be you lowest
these steps were executed using a for loop inside a while loop.

Hope this helps!


#4

Oh buggers! I hadn’t even noticed the 12 vs 60 issue! I bet that’s where the mistake is! Grrrr! Thanks so much for spotting that, I’ll play with that and see if it fixes the whole problem!


#5

The issue ArielLeslie brought up was the problem. I added in one simple

if (biggerNum % smallerNum === 0) {
    return biggerNum;
  }

to my LCM() function, and it solved the whole issue… I’ve been struggling on this one for DAYS! Thanks so much!!