Also posted on virenb.cc
Let's solve freeCodeCamp's intermediate algorithm scripting challenge, 'Smallest Common Multiple'.
Starter Code
function smallestCommons(arr) {
return arr;
}
smallestCommons([1,5]);
Instructions
Find the smallest common multiple of the provided parameters that can be evenly divided by both, as well as by all sequential numbers in the range between these parameters.
The range will be an array of two numbers that will not necessarily be in numerical order.
For example, if given 1 and 3, find the smallest common multiple of both 1 and 3 that is also evenly divisible by all numbers between 1 and 3. The answer here would be 6.
Test Cases
-
smallestCommons([1, 5])
should return a number. -
smallestCommons([1, 5])
should return 60. -
smallestCommons([5, 1])
should return 60. -
smallestCommons([2, 10])
should return 2520. -
smallestCommons([1, 13])
should return 360360. -
smallestCommons([23, 18])
should return 6056820.
Our Approach
After reading the starter code, instructions, and test cases, this is what I summarized about this challenge -
We have one input, an array with two indexes, always positive numbers.
We must return a number.
We have another math based challenge, just like yesterday's. We'll look more at the formula of what is commonly referred to as Least Common Multiple (LCM).
From ThinkMath, a multiple (of a number) is any product of that number and an integer.
It is often useful to know what multiples two numbers have in common. One way is to list (some of) the multiples of each and look for a pattern. For example, to find the common (positive) multiples of 4 and 6, we might list:
- Multiples of 4: 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, ...
- Multiples of 6: 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, ...
The numbers 12, 24, 36, and 48 appear on both of these lists (and more would appear if the lists were longer). They are common multiples. The least common multiple is the smallest of these: 12. All the other common multiples are, themselves, multiples of the least common multiple.
We'll touch on the math and the challenging part in more detail soon.
I'll start off the challenge by using sort()
on arr
, to make sure the bigger number is the first index.
arr = arr.sort((a,b) => b - a);
Next, I'll save each value into their own variable. We can do that by destructuring arr
.
let arr = [100, 50];
let [high, low] = arr;
console.log(high);
// 100
console.log(low);
// 50
// Instead of
let arr = [100, 50];
let high = arr[0];
let low = arr[1];
So it looks like we will use a for
loop to check on the divisibility of these two numbers (and the sequence of numbers in between). Before I start the loop, I will declare one more variable:
let multiple = high;
I'm setting multiple
to the larger variable, high
.
For our for
loop, it will run as long as low
is smaller than high
. See the below code -
for (let i = low; i < high; i++) {}
So, looking at our test cases, let's disect [5, 1]
. Without any code, what are the multiples (the answer should be 60):
5: 1, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70
1: 1, 2, 3, 4, 5
So 5 is the smallest common multiple but we want a number that is evenly divisible by all the numbers between 1 and 5. This is the real challenge. So just doing some math without code, we can study the above numbers and determine 60 is the first number that is divisble evenly by 1, 2, 3, 4, 5.
For example, if given 1 and 3, find the smallest common multiple of both 1 and 3 that is also evenly divisible by all numbers between 1 and 3. The answer here would be 6.
So in our for
loop, we can first check if multiple
is not divisible by low
. If it is not, we will add the value of high
to multiple
, then reduce our i
variable and keep looping.
if (multiple % 1 !== 0) {
multiple += high;
i = low - 1;
}
We can add an else if
statement, if i
equals high
, we know we have found our answer. Let's see how this works step by step.
function smallestCommons(arr) {
arr = arr.sort((a,b) => b - a);
let [high, low] = arr;
let multiple = high;
for (let i = low; i < high; i++) {
if (multiple % i !== 0) {
multiple += high;
i = low - 1;
}
else if (i == high) {
return multiple;
}
return multiple
}
Starting the for
loop,
-
i = 1, multiple = 3
- 3 / 1 = 0 reminder so we ignore the
if
statement (and also theelse if
)
- 3 / 1 = 0 reminder so we ignore the
-
i = 2, multiple = 3
- 3 /2 = 1 remainder, so we add
high
tomultiple
and also set i = low - 1; - i = 0 but next loop we i++
- 3 /2 = 1 remainder, so we add
-
i = 1, multiple = 6
- 6 / 1 remainder is 0 so we don't increment multiple
-
i = 2, multiple = 6
- 6 / 2 remainder is 0 so we don't increment multiple
- next loop, with i++, i is no longer less than high so we exit the for loop
We return multiple
This may not be the most efficient solution!
Our Solution
function smallestCommons(arr) {
arr = arr.sort((a,b) => b - a);
let [high, low] = arr;
let multiple = high;
for (let i = low; i < high; i++) {
if (multiple % i !== 0) {
multiple += high;
i = low - 1;
}
else if (i == high) {
return multiple;
}
return multiple;
}
}
Links & Resources
'Smallest Common Multiple' Challenge on fCC
Thank you for reading!
Top comments (0)