Smallest Common Multiple Feedback

Smallest Common Multiple Feedback
0

#1

First off, my apologies if this is in the wrong area. I wasn’t sure where to put it since it’s not an actual fcc “project” and I don’t need help as I’ve completed the challenge. Just looking for some general feedback and wondering if I over complicated the challenge. This is by far the longest piece of code I’ve written for one of these challenges, I’m just proud I actually got it done. Any feedback would be greatly appreciated. Specifically, I tried to take a functional programming approach and define functions that did as little as possible to make it more modular if I ever needed to change anything. Clearly, some of the individual functions are a little long and do more than one thing but approaching the problem from this angle of writting functions to process each step little by little was the only way I could wrap my head around tackling this challenge.

// function to find LCM
function smallestCommons(arr) {

// determine all factors
var range = rangeFinder(arr);

// check if factors are prime and return multidimensional arr with only prime factors
var primeCheck = primeChecker(range);  

// find the greatest occurence of prime factors per primeCheck element
var checker = check(primeCheck);

// multiple each prime factor by the number of times it occurs and multiple the products of each result together for LCM
var lcm = lowest(checker);

return lcm;
}

// find range of numbers 
function rangeFinder(arr) {
  var x = arr[0];
  var y = arr[1];
  var rangeArr = [];

  if (x > y) {
    for (var i = y; i <= x; i++) {
      rangeArr.push(i);
    }
  } else {
    for (var j = x; j <= y; j++) {
      rangeArr.push(j);
    }
  } 
  return rangeArr;
}

// check if a number is prime
function isPrime(num) {
  if (num % 1 === 0) {
    var primeCount = 0;

    for (var i = num; i > 0; i--) {
      if (num % i === 0) {
        primeCount++;
      }
    }
    if (primeCount > 2) {
      return false;
    } else {
      return true;
    }    
  } else {
    return false;
  }
}

// run range array through prime checker
function primeChecker(arr) {
  var primedArr = [];
  for (var i = 0, length = arr.length; i < length; i++) {
    primedArr.push(factorToPrime(arr[i]));
  }
  return primedArr;
}

// reduce non-prime factors to prime factors
function factorToPrime(num) {
  if (num > 1) {
    var divisor = 2;
    var factorArr = [];
    if (!isPrime(num)) {
      while(!isPrime(num/divisor)) {
        if ((num/divisor) % 1 !== 0) {
          divisor++;
          while(!isPrime(divisor)) {
            divisor++;
          }
        } else {
          factorArr.push(divisor);
          num /= divisor;
          divisor = 2;      
        }
      }
      factorArr.push(num / divisor, divisor);
    } else if (isPrime(num)) {
      return num;
    }
    return factorArr;
  } else if (num === 1) {
    return num;
  }
}


// check which prime number occurs the most per factor
function check(arr) {
  var countArr = [];
  for (var i = 0, length = arr[arr.length - 1]; i < length; i++) {
    countArr[i] = 0;
  }

  for (var i = 0, length = arr.length; i < length; i++) {
    if (isPrime(arr[i])) {
  
      countArr[arr[i] - 1] = 1;
    } else {
      for (var j = 0, length2 = arr[i].length; j < length2; j++) {
        if (countInArray(arr[i], arr[i][j]) > countArr[arr[i][j] - 1]) {
          countArr[arr[i][j] - 1] = countInArray(arr[i], arr[i][j]);
        }
      }      
    }
  }
  return countArr;
}

// counts how many times an element occurs in an array
// used to determine the greatest occurrence of each prime factor respective to the elements in primeCheck
function countInArray(array, what) {
  var count = 0;
  for (var i = 0; i < array.length; i++) {
    if (array[i] === what) {
      count++;
    }
  }
  return count;
}

// multiply to find lcm
function lowest(arr) {
  var lcm = 1;
  for (var i = 0, length = arr.length; i < length; i++) {
    if (arr[i] > 0) {
      lcm *= exponential(i + 1, arr[i]);
    }
  }
  return lcm;
}

// find the product for each prime factor
function exponential(a, b) {
  var i = 0;
  var product = 1;
  while (i < b) {
    product *= a;
   i++;
  }
  return product;
}

#2

Good job solving the challenge! You might want to look into the “Euclidean algorithm” for the logic.

I used Math.max() and Math.min() to find the high and low values in arr.

There are multiple suggested solutions and even more solutions in the comments if you click on the hints button near the submit button in the challenge.


#3

Thanks for the feedback I’ll definitely look into the algorithm. I looked up how to find the least common multiple on some math websites and then translated their steps into code which is how I came to my result.


#4

I don’t think your solution is overcomplicated - there are some obvious simplifications like anything mod 1 is zero i.e. n % 1 === 0 is true for any integer n - also instead of two cases to handle the bigger of a pair of numbers you can first find the max and have just one case

you have actually done a really great job of coding up the literal definition of lcm - the challenge now is to incrementally improve and refine your solution

lcm is a pure math problem - specifically from number theory - most likely a better solution needs mathematical improvements more than code optimizations

instead of looking up known solutions or algorithms why not analyze the math of computing lcm?

let’s look at the 18-23 testcase - we need lcm(18,19,20,21,22,23)

the first thing to realize is lcm is commutative

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

and associative

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

this means order does not matter and lcm can be computed iteratively

lcm(18,19,20) can be calculated as ans=lcm(18,19) then lcm(ans, 20)

let’s look at lcm(18,19,20)

lcm(18,19): 18*19 = 342 is right
lcm(342, 20): 342 * 20 = 6840 is wrong - it’s actually 3420 - but why?

because 342 and 20 have 2 as a common factor so lcm(342,20) = 6840/2 = 3420

342 = 2 * 3 * 3 * 19
20  = 2 * 2 * 5

why can the product be reduced by a common factor- because the simple product is a product of all the prime factors

if a prime factor is duplicated it can be removed once from the product - the smaller product still contains all prime factors for both numbers meaning the smaller product is still divisbile by both numbers

lcm(342, 20) = (2 * 3 * 3 * 19) * (2 * 2 * 5) / 2
             = (2 * 3 * 3 * 19) * (2 * 5)

this insight leads to some big improvements in the computation that you can make to your code


Smallest Common Multiple - Recursion
#5

I didn’t look up an algorithm specifically. I actually went and looked up the actual math behind finding the lowest common multiple and from the pure math I abstracted it into an algorithm that I could actually code. Because I didn’t look at anyone else’s code, the only way I could actually wrap my head around the problem was to break each step down as much as I could to tackle each step behind the theory of LCM. It was definitely challenging but I agree with you at this point all that’s left is to refactor the code into a more elegant based on the actual mathematical theory. Thanks for looking at my code though I really appreciate the feedback!


#6

These are the actual websites where I found the theory behind LCM.

Site 1 Theory for LCM

Site 2 Prime Factorization (which is necessary for determining LCM)

From these two links I abstracted the algorithm that I eventually turned into my solution.


#7

continuing my previous post …

the reduction due to one common prime factor must be carried out for every common prime factor - this leads to two ways to restate lcm

lcm(a,b) is the product of the bigger power of each prime factor from factorizations of a and b

the bigger prime powers from the factorizations of 342 and 20 are

2^2 (from 20), 3^2 (from 342), 5^1 (from 20), 19^1 (from 342) - so

lcm(342, 20) = 2**2 * 3**2 * 5 * 19 = 3420

you used this first restatement in your solution just not iteratively

computationally this still relies on prime factorization which is quite expensive

another way to restate lcm(a,b) is to note the product of all the common prime factors of two numbers is their gcd - so

lcm(a,b) = a*b / gcd(a,b)

so

lcm(342, 20) = 342*20 / gcd(342, 20) = 3420

what’s interesting about the second restatement is it does not directly use prime factorizations

if there was a simpler way to calculate the gcd without factorization we’d be golden


Smallest Common Multiple - Recursion
#8

Just a couple comments first:

Because it is true for every integer is exactly why I used it as a test case. Because of the way isPrime and factorToPrime work together some quotients ended up being real numbers. isPrime returns real numbers as true which as we know is outside the definition of a prime number. So the fact the test returns true only on integers is why the mod is there.

I ran into this problem and, as provided in the second link, the reason this occurs is because you do not use the “2” from the prime factorization of “342”, you would only use the two “2’s” from twenty because the occurrence of “2” is higher in “20” than “342” (in the example of only 20 and 342). So if you remove the lone “2” and only multiply 3 * 3 * 19 * 2 * 2 * 5 it will give you the 3420. The same is true for all numbers in the range. So from 18 - 23 you would only use the prime numbers with the highest occurrence across the board. This is the purpose of primeCheck (which is a variable that contains the output of the function primeChecker that goes through the range of 18-23 and collects all the prime factors of each number in the range). The output from primeCheck in this case would be [[2, 3, 3], 19, [2, 5, 2], [7, 3], [11, 2], 23]. Each index of this array is a number from the range 18-23. If the index itself is a nested array it’s because the number at that index wasn’t prime and thus needed to be factored down to its prime components. From there the check function goes through this array to find which index contains the highest occurrence of each prime number respectively. In this case, index 2 contains two “2’s”, index 0 contains two “3’s”, index 2 contains one “5”, index 3 contains one “7”, and so on until all prime factors in the array are account for. It eventually works out to 2 * 2 * 3 * 3 * 5 * 7 * 11 * 19 * 23 = 6056820 which is the LCM. So I suppose we had the same idea and it didn’t matter which duplicate was removed because as you stated already it is associative.

Could you eleborate more on this? To my knowledge loops are iterative and in each function there is either a for loop or a while loop that iterates over an array.

Doesn’t the restatement use prime factorization in its call to gcd?
I could be wrong as it’s just an abstraction but it seems to me that gcd would need to utilize prime factorization? If the gcd is using prime factorization how is it less expensive in the case than the former?

Again thank you for responding to this, I have no one that I can have these kinds of conversations with and bounce algorithmic/programming ideas off of in real life so all your input and ideas are greatly appreciatd.


#9

Use Math.floor or Math.ceil to insure some arithmetic results in an integer e.g. Math.floor(7/2) gives 3 as the quotient - don’t pass real numbers to functions that only make sense for integers like a primality checker - if you must you can use Number.isInteger but its use may indicate a weakness in your algorithm

Your solution is not iterative - your loops fill one complete array after another - the lcm is computed at the very end using an array full of intermediate values - an iterative solution computes and updates the lcm using an input value- at any point in the iteration the lcm is known for the values processed from the original input before any remaining values are processed. Imagine being fed the input one number at a time - 18 then 19 then 20 then 21 … - your solution has to wait for the end of the input to begin computing the lcm - an iterative or incremental solution would compute the lcm for 18 then update it for 19 then update for 20 etc

No - lcm(a, b) = a*b/gcd(a, b) does not mention prime factorization per se. We were led to gcd using common prime factors that came up in lcm but the definition of gcd does not mandate the use of prime factorization - I guess this realization is what we owe Euclid

after reformulating lcm as a gcd problem we get to play Euclid and ask how could we compute gcd(a,b) without prime factorization? if you can figure this out on your own you would have been considered a genius around 2,500 years ago


#10

As it stands Math.floor and Math.ceil would break the program as it is written. The idea is to iterate the divisor through each prime number (2,3,5,7…) until the quotient is an integer. So if the quotient is a real number iterate the divisor until it’s a prime number and then try the division again. Math.floor and Math.ceil wouldn’t produce the correct result if they turned the real numbers into integers.


#11

sure - but isn’t the goal now to improve your solution and code?


#12

Absolutely, I thought you meant to use those in the current iteration of my code. You’ve given me some great pointers. I definitely appreciated the feedback. Iterative and recursive programming is still something I struggle to wrap my head around when it comes to actually writing the code out so refactoring this will give me some much needed practice. Thanks a bunch!