-This particular problem can be confusing because most people look for the smallest common multiple of the two number but forget the keyword **range.** This means that if you get `[1,5]` then you have to check for the smallest common multiple for all these numbers [1,2,3,4,5] that is evenly divisible by all of them.
+The smallest common multiple between two numbers is the smallest number that
+both numbers can divide into. This concept can be extended to more than two
+numbers as well.
+
+We can first start with just finding the smallest common multiple between two
+numbers. Naively, you can start writing out multiple of each number until you
+write a multiple that exists from both numbers.
+
+An example would be the numbers `3` and `4`. The multiples of `3` are `3, 6, 9,
+12, 15, 18, ...` and the multiples of `4` are `4, 8, 12, 16, 20, ...`. The
+first smallest number we run into in both lists is `12` so this is the smallest
+common multiple between `3` and `4`.
+
+This problem can be confusing because most people look for the smallest common
+multiple of just the two numbers but forget the keyword **range**. However, this
+means that if you are given `[1,5]`, then you have to check for the smallest
+common multiple for all the numbers `[1,2,3,4,5]` that is evenly divisible by
+all of them.
##Hint: 1
-Create an array with all the numbers that are missing from the original array to make it easier to check when having to check for even division.
+Create an array with all the numbers that are missing from the original array to
+make it easier to check when having to check for even division.
##Hint: 2
-You can use modulo `%` to check if the reminder is 0, which means it is evenly divisible.
+You can use remainder operator (`%`) to check if the reminder of a division is
+0, which means it is evenly divisible.
##Hint: 3
-If you sort the array from greater to lowest then you can check for the first two numbers as it is more likely to the the smallest common multiple than the lower numbers.
+If you sort the array from greatest to smallest, then you can use the first
+two numbers as a first check for the smallest common multiple. This is because
+they are more likely to be the smallest common multiple than the lower numbers.
-// Create new array and add all values from greater to smaller from the original array.
+// Create new array and add all values from greater to smaller from the
+// original array.
var newArr = [];
for (var i = arr[0]; i >= arr[1]; i--) {
newArr.push(i);
@@ -36,7 +58,7 @@ function smallestCommons(arr) {
var loop =1;
var n;
-// run code while n is not the same as the array length.
+// Run code while n is not the same as the array length.
do {
quot = newArr[0] * loop * newArr[1];
for (n =2; n <newArr.length; n++) {
@@ -53,58 +75,81 @@ function smallestCommons(arr) {
```
#Code Explanation:
-- Because the possibility of the smallest common denominator being among the two biggest numbers, it makes sense to check those first, so sort the array.
-- Create a new array to sore all the numbers.
-- Use a descending for loop to add the numbers from the biggest to the smallest in the new array.
-- Declare the variables for the quotient, the number of loops and the variable that we will use in a for loop on another scope, this will allow us access outside the loop.
-- Use a do while loop to check what we need while **n** is not the same length as the new array.
-- In the **do** part, we are going to multiply the very first number, times the number of loops, times the second number.
-- The loop part will allows us to increase the number beyond the greatest number we have without having to change the algorithm.
-- We enter a for loop that will go from n being 2 and going up by one while it is smaller than the array with all the numbers.
-- If the quotient is not even then stop the loop. If it is even then it check for the next elements in the array until it is not even or we find our answer.
-- Outside the loop, increase the value of loop.
-- At the end of the loop return the quotient.
-
-If the array only has two elements then the for loop never gets used and the return value is the product of said numbers. Otherwise, from the third element and until n is the same and the array length check if the remainder of the quotient and the third value of the array is not 0, if it is not 0 then stop loop increases and then we start over. If the remainder was 0 then keep checking until the end of the array.
+- Because of the possibility of the smallest common denominator being among the two
+ biggest numbers, it makes sense to check those first, so sort the array.
+- Create a new array to sort all the numbers, `newArr`.
+- Use a descending `for` loop (`var i = arr[0]; i >= arr[1]; i--`) to add the
+ numbers from the biggest to the smallest in the new array.
+- Declare the variables for the quotient so we can access them outside the loop:
+ - the quotient that'll be our smallest common multiple (`quot`)
+ - the loop number we're checking (`loop`)
+ - the index of the array of numbers (`n`)
+- Use a `do``while` loop to check what we need while `n` is not the same length
+ as the new array.
+- In the `do` part, we are going to multiply the very first number, times the
+ number of loops, times the second number (`quot = newArr[0] * loop *
+ newArr[1];`).
+- The `loop` part will allows us to increase the number we're checking beyond
+ the greatest number we have without having to change the algorithm.
+- We enter a `for` loop that will go from `n` being 2 and going up by one
+ (`loop++`) while it is smaller than the array with all the numbers (`n <
+ newArr.length`).
+- If the quotient does not divide evenly (`quot % newArr[n] !== 0`), then stop
+ the loop (`break;`). If it is even, then check for the next elements (`n++`)
+ in the array until it is not even or we find our answer.
+- Outside the loop, increase the value of loop (`loop++`).
+- At the end of the loop return the quotient (`return quot;`).
+
+Note: If the array only has two elements, then the `for` loop never gets used
+and the return value is the product of said numbers.
#Alternate solution:
-Note: The solution above requires over 2,000 loops to calculate the test case smallestCommons([1,13]), and over 4 million loops to calculate smallestCommons([1,25]). The alternate code below evaluates smallestCommons([1,13]) in around 20 loops and smallestCommons([1,25]) in 40, by using a more efficient algorithm.
+Note: The solution above requires over 2,000 loops to calculate the test case
+`smallestCommons([1,13])`, and over 4 million loops to calculate
+`smallestCommons([1,25])`. The alternate code below evaluates
+`smallestCommons([1,13])` in around 20 loops and `smallestCommons([1,25])` in
+40, by using a more efficient algorithm.
```js
functionsmallestCommons(arr) {
-for(i =Math.max(...arr); i >=Math.min(...arr); i--) arr.push(i);
-
-returnarr.slice(2).reduce(function(x,y){
-var a = x, b = y, t =0;
-while(a % b){a = a % b; t = a; a = b; b = t;}
+for(i =Math.max(...arr); i >=Math.min(...arr); i--) { arr.push(i); }
+
+returnarr.slice(2).reduce(function(x,y) {
+var a = x, b = y, t =0;
+while(a % b) { a = a % b; t = a; a = b; b = t;}
return x / b * y;
});
}
-
```
-If you have trouble understanding the .reduce() method, you can compare it to this code, which essentially does the same thing:
+If you have trouble understanding the `.reduce()` method, you can compare it to
+this code, which essentially does the same thing:
```
function smallestCommons(arr) {
- for(i = Math.max(...arr); i >= Math.min(...arr); i--) arr.push(i);
-This code is based on the [Euclidean algorithm](https://en.wikipedia.org/wiki/Euclidean_algorithm) for finding smallest common multiples.
+This code is based on the [Euclidean
+algorithm](https://en.wikipedia.org/wiki/Euclidean_algorithm) for finding
+smallest common multiples.
#Credits:
-If you found this page useful, you can give thanks by copying and pasting this on the main chat: **`thanks @Rafase282 @Adoyle2014 for your help with Algorithm: Smallest Common Multiple`**
+If you found this page useful, you can give thanks by copying and pasting this
+on the main chat: **`thanks @Rafase282 @Adoyle2014 @erictleung for your help
+with Algorithm: Smallest Common Multiple`**
->**NOTE:** Please add your username only if you have added any **relevant main contents** to the wiki page. (Please don't remove any existing usernames.)
+>**NOTE:** Please add your username only if you have added any **relevant main
+> contents** to the wiki page. (Please don't remove any existing usernames.)
erictleung
committed
0 comments on commit
bc608a0