Would love feedback for the SmallesCommonMultiple task

Would love feedback for the SmallesCommonMultiple task
0

#1

Hi, I solved the SmallesCommonMultiple and it was great. However I was surprised by the complexity and length of my solution. If possible please take a look at the code, and let me know if there are simpler methods I could be using. THANKS. http://codepen.io/bencarp/pen/dvWXgq

@YankeeDK @pachecot @Reggie01 @kevcomedia @vdineva


#2

That was a tough challenge for sure. My old code was quite large, messy, and slow - I swear the lights dimmed when I ran it and I heard some car alarms in the distance. NORAD may have scrambled some jets. I ended up starting from scratch and came up with this:

function smallestCommons(arr) {

  var full = arr.sort();

  var max = arr[1]; // the largest of the numbers in the array
  var lcm = 0;
  var notDone = true;
  
  while (notDone) {
    lcm+=max; // lcm MUST be a mutliple of max so increment by max
    for (var j = arr[0] ; j <= max ; j++) {
      if (lcm % j !== 0) {
        break;
      }
      else if (j == max-1) { // no need to check max - already a multiple
        notDone = false;
      }
    } // for j
  } // while

  return lcm;
}

smallestCommons([1,5]);

I start by sorting the array.

The while loop checks to each candidate lcm. We know that the lcm must be a multiple of the largest number in the array, so we’ll start there and index by that number (max). (A lot of the algorithms I see miss this simple time saver.)

The j loop checks each number from the lowest to the highest of the array numbers. If one of them has ((lcm % j !== 0) then we know that it is not the true lcm so we break and try the next candidate lcm (no need to keep checking that candidate lcm. Many people keep checking for some reason.)

When if fails the if statement, and we made it to the number below max then we know that we have the true lcm. There is no need to check max since we’ve been indexing by that - each of our candidate lcms is a multiple of max by definition. (Another way we saved some time.)

I’m pretty pleased with how it turned out. But I did go through hell to get there.


#3

It’s interesting to note that, to compute the LCM of three numbers, you first compute the LCM of two of them, then compute the LCM of that result and the remaining third number.

lcm(a, b, c) = lcm( a, lcm( b, c ) )

You can also do the same for any number of numbers.

What this means is that, you can create a function that computes the LCM of just two numbers, then compute for the LCMs piecemeal. It’s much simpler than trying to compute for the LCM of the numbers all at once.

What I did is create an array of numbers from the input (if the input is [1, 5], my array is [1, 2, 3, 4, 5]), then use .reduce with the LCM function as callback.


#4

Both of the solutions u suggested are very elegant and simple. Oh, I worked hard on my solution, which was elegant as well, but obviously way way over complicated.
Nice! Thank you.
@kevcomedia @ksjazzguitar


#5

By the way, personally I think there was no need to explain in words as your code (and comments) speaks for itself.