Smallest Common Multiple - easy mode

JavaScript
1

Hello!

I am trying to solve this task using well known techniques. I outlined a plan (express necessary actions on paper), wrote a pseudo code. Then I implemented it step by step. First I made the code to calculate GCD only. Then LCM. Now that I try to combine the two, I ran into troubles which are more syntax related I think.

So this code calculates LCM for first two numbers, then second and third numbers, then third and fourth, etc.

function smallestCommons(arr) {
//creating an array with two given numbers as start and end points
let newArr=[] 
  if (arr[0]<arr[1]){
      for (let i = arr[0]; i<=arr[1];i++){
      newArr.unshift(i) 
    }
  } else if (arr[0]>arr[1]){
    for (let j=arr[0]; j>=arr[1];j--){
      newArr.push(j)
    }
  }
console.log(newArr)
  for (let x=0;x+1<newArr.length;x++){
//gcd calculation
  let a=newArr[x]
  let b=Math.floor(newArr[x]/newArr[x+1])
  let r=newArr[x]%newArr[x+1]
  let q=Math.round(newArr[x]/newArr[x+1])
    do {
    a=b*q+r
    a=b
    b=r
    q=Math.round(a/b)
    r=a%b   
    } while (r>0)
//lcm calculation
  let lcm = (newArr[x]* newArr[x+1])/q
  }
}

What I need is to calculate LCM from first two numbers, then calcualte LCM from the first LCM and the third number, then calculate LCM from second LCM and fourth number, etc.

In my opinion, it should work if I fix a to lcm, but it does not. What am I missing?

function smallestCommons(arr) {
//creating an array with two given numbers as start and end points
let newArr=[] 
  if (arr[0]<arr[1]){
      for (let i = arr[0]; i<=arr[1];i++){
      newArr.unshift(i) 
    }
  } else if (arr[0]>arr[1]){
    for (let j=arr[0]; j>=arr[1];j--){
      newArr.push(j)
    }
  }

  for (let x=0;x<newArr.length;x++){
//gcd calculation
  let a=newArr[0]
  let b=Math.floor(a/newArr[x])
  let r=a%newArr[x]
  let q=Math.round(a/newArr[x])
    do {
    a=b*q+r
    a=b
    b=r
    q=Math.round(a/b)
    r=a%b   
    } while (r>0)
//lcm calculation
  let lcm = (a*newArr[x])/q
  console.log(lcm)
  a = lcm
  return lcm

  }
}

I hope at least I get the math right.

2

Taking a step by step approach I formulated a simpler question.

is the following approach reasonable?

  1. Creating a loop
  2. Calculating the LCM of first two items
    ------2.1. Calculating GCD of first two items
    -------2.2. Calculating LCM of first two items using the GCD
  3. Looping to the third item and calculatiing the LCM of the third item and the first calculated LCM
  4. and so forth
3

That’s a valid approach but your codes pretty complicated for that approach

4

Thank you. Do you refer to the GCD formula execution?
Could you suggest an approach? If that approach has a name and it is not just common sense approach :slight_smile:

5

I’d look at Wikipedia for one of the algorithms available there.

It also probably would be easier to read your logic if you made small GCD and LCM helper functions.

1 Like