What Sorcery is this? | Intermediate Algorithm Scripting: Smallest Common MultiplePassed

JavaScript
1

As usual, I only check the hints button after a solution is found. Then we proceed to investigate more effective/interesting ones posted there.

There was is one elegant answer by @JanEgbers that I can’t ignore. It’s way more compact then my litte monster, and so far I couldn’t understand how it actually works.

Anyways, there it goes:

function smallestCommons(arr) {

  var max = Math.max(arr[0], arr[1]);
  var min = Math.min(arr[0], arr[1]);
  var mltple = max;

  for(var i = max; i >= min; i--){
    if(mltple % i !== 0){
      mltple += max; 
      i = max;
    } 
  }

  return mltple;  
}

My little monster:

function smallestCommons(arr) {

  let a;
  let b;
  let sequence = [];
  let multiplier = 1;

  //put smaller element at 'a' and bigger at 'b'.
  if (arr[0] > arr[1])
    {a = arr[1]; b = arr[0];} else 
    {a = arr[0]; b = arr[1];}

  //make an full sequence array
  for (let c = a; c <= b; c++) {
    sequence.push(c);
  }

  //check if n is a multiple of everyone in the sequence array
  let answerFound = (n) => {
    return sequence.map(e => n % e == 0)
                   .every(e => e)
  }
  
  //immediately-invoked-recursive function multiplies  
  //the biggest number until an answer is found.
  return (function recAnswer(answ, mul){
   return answerFound(answ*mul) ? answ*mul : 
                                  recAnswer(answ, mul+1);
  })(b, multiplier);
}
//test below
console.log(smallestCommons([2,5]));

Maybe I need more coffee, already late…

2

Oh heavens… One minute after posting and the answer came by. Maybe more coffee was needed indeed. Its so simple - and clever!

What was bugging me out was

if(mltple % i !== 0)

As ‘i’ started as the same number ‘mltple’, the if would always evaluate ‘false’ and do nothing, hence the confusion.

The magic happens after that: the loops simply continues with the next lower sequence number, and will add for the next multiple, reseting ‘i’ until the SCM of both is found.

It will then test the next sequence number, and so on, until the SCM of the sequence is found.

I’m baffled by how this problem could be solved with such a simple approach!

Side question: Is that the most performant answer so far?

1 Like
3

You can get better performance if you use the fact that LCM(a, b, c…) = LCM(a, LCM(b, c…)), the LCM formula from the GCD, and an efficient GCD algorithm, but this is pretty good for loop based approach.

4

Remember that it is not your job to reinvent mathematics. If you don’t know the most efficient way to find lcm, or primes, etc, there’s nothing wrong with getting the math from Wikipedia. :upside_down_face:

1 Like
5

Yup. That is my main source for these Euler type problems.

6

Your code has been blurred out to avoid spoiling a full working solution for other campers who may not yet want to see a complete solution. In the future, if you post a full passing solution to a challenge and have questions about it, please surround it with [spoiler] and [/spoiler] tags on the line above and below your solution code.

Thank you.

7

Oh, thank you.

I was too sleepy to recall the tags . Won’t happen again :+1: