-
Notifications
You must be signed in to change notification settings - Fork 0
/
alg14-smallestCommonMultiple.js
118 lines (108 loc) · 3.5 KB
/
alg14-smallestCommonMultiple.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/*
Source: <https://www.freecodecamp.org/learn/javascript-algorithms-and-data-structures/intermediate-algorithm-scripting/smallest-common-multiple>
Smallest Common Multiple
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.
*/
function mySmallestCommons(arr) {
return arr;
}
/*
Get a help > Get a hint <>
*/
//Solution 1
function smallestCommons1(arr) {
// Setup
const [min, max] = arr.sort((a, b) => a - b);
const numberDivisors = max - min + 1;
// Largest possible value for SCM
let upperBound = 1;
for (let i = min; i <= max; i++) {
upperBound *= i;
}
// Test all multiples of 'max'
for (let multiple = max; multiple <= upperBound; multiple += max) {
// Check if every value in range divides 'multiple'
let divisorCount = 0;
for (let i = min; i <= max; i++) {
// Count divisors
if (multiple % i === 0) {
divisorCount += 1;
}
}
if (divisorCount === numberDivisors) {
return multiple;
}
}
}
//Solution 2
function smallestCommons2(arr) {
// Setup
const [min, max] = arr.sort((a, b) => a - b);
const range = Array(max - min + 1)
.fill(0)
.map((_, i) => i + min);
// Largest possible value for SCM
const upperBound = range.reduce((prod, curr) => prod * curr);
// Test all multiples of 'max'
for (let multiple = max; multiple <= upperBound; multiple += max) {
// Check if every value in range divides 'multiple'
const divisible = range.every((value) => multiple % value === 0);
if (divisible) {
return multiple;
}
}
}
//Solution 3
function smallestCommons3(arr) {
// Setup
const [min, max] = arr.sort((a, b) => a - b);
const range = Array(max - min + 1)
.fill(0)
.map((_, i) => i + min);
// GCD of two numbers
// https://en.wikipedia.org/wiki/Greatest_common_divisor#Euclid's_algorithm
const gcd = (a, b) => (b === 0) ? a : gcd(b, a % b);
// LCM of two numbers
// https://en.wikipedia.org/wiki/Least_common_multiple#Using_the_greatest_common_divisor
const lcm = (a, b) => a * b / gcd(a, b);
// LCM of multiple numbers
// https://en.wikipedia.org/wiki/Least_common_multiple#Other
return range.reduce((multiple, curr) => lcm(multiple, curr));
}
//Solution 4
// Find the SCM of a range of numbers
function smallestCommons4(arr) {
let primeFactors = {};
const [min, max] = arr.sort((a, b) => a - b);
for (let i = min; i <= max; i++) {
// Factorize number in range
let primes = getPrimeFactors(i);
for (let j in primes) {
// Add factor to set or update number of occurrences
if (!primeFactors[j] || primes[j] > primeFactors[j]) {
primeFactors[j] = primes[j]
}
}
}
// Build SCM from factorization
let multiple = 1;
for (let i in primeFactors) {
multiple *= i ** primeFactors[i]
}
return multiple;
}
// Compute prime factors of a number
function getPrimeFactors(num) {
const factors = {};
for (let prime = 2; prime <= num; prime++) {
// Count occurances of factor
// Note that composite values will not divide num
while ((num % prime) === 0) {
factors[prime] = (factors[prime]) ? factors[prime] + 1 : 1;
num /= prime;
}
}
return factors;
}