Down to my last few intermediate challenges - Smallest Common Multiple

Down to my last few intermediate challenges - Smallest Common Multiple
0

#1

Hi everyone.

I am having some trouble with this problem. Specifically, I don’t understand how to factor in the fact that a number outside the range of values could divide the LCM value into a smaller number.

i.e.

function smallestCommons(arr) {
  var b = [];
  var c = [];
  if (arr[1]<arr[0]){
    c[0]=arr[0];
    c[1]=arr[1]; 
  } else {
    c[0]=arr [1];
    c[1]=arr[0];   
  }
  for(var i=c[1];i<=c[0]; i++) {
    b.unshift(i);
  }
  var lCM = b.reduce(function(acc,val){
    if (acc % val != 0) {   
      return acc = acc * val;
    } else {
      return acc;
    }
  });

  return lCM;
}


smallestCommons([23, 18]);

`
For example, an input of [23,18] with this code gives an answer of 72,681,840. The true answer is 6,056,820 (my answer divided by 12). I’m not seeing a way around this and may need a fresh perspective. I have burned through the hints. I have 6 intermediate challenges left and they are all leaving me stumped!

Thanks,

Jim


#2

I think reduce is not well suited to this task. LCM will always be the largest possible multiple in your range, and you want the smallest. If you use a for loop, you can terminate it as soon as you find your answer.


#3

You can use lcm & gcd formulas from wikipedia
https://wikimedia.org/api/rest_v1/media/math/render/svg/9453a93953efe119b7502c1827aeeb869ab121d6


#4

That’s not how the smallest common multiple works. Take for example 4, 5, and 6. Let’s say that your reduce function makes it to the last element (6) and checks if accumulator%current value!=0, which translates to 20%6!=0, which is true, so you you get 120 as the smallest common multiple, which is not true (60 is smaller).

Instead, you need to break each number into its prime number components, so that
4=2 * 2
5=5
6=2 * 3
and then make a list with all the prime number components and choose the prime number at the largest power.
In this example, the list would be 2, 3, 5 and 2 would be at the power of 2, 3 at the power of 1 and 5 at the power of one. Multiplied, this means 4* 3 * 5 = 60.


#5

There is more than one way to compute scm and using factorization is hardest.


#6

I spent a lot of time on this problem. The way I tackled it was looking up the mathematical logic for LCM and then translated each step into code.


#7

I think that’s how I did it, if I recall correctly, after some time on Khan Academy.

Yes - it was very hard. This algorithm was the one that made me feel the most like an idiot :slight_smile: