Smallest Common Multiple Feedback

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

1 Like