AtActionPark - 1 year ago 51

Javascript Question

**TLDR:** I'm looking for an algo that returns the smallest possible least common multiplier for a variable array of numbers while knowing:

- one of the numbers
- the size of my array
- the min and max values possible for the numbers

I’m working with a music app and have an algo problem:

When mixing different rhythms (each with a different number of steps), I need to compute the resulting number of steps for the result to loop. This is done easily with a least common multiplier calculation.

Lets assume I have a lengths array that contains all the different lengths in steps

`var lengths = [4,5,6,8]`

//greatest common denominator

function gcd(a,b){

var t,b,a

while(b != 0){

t = b;

b = a%b

a=t

}

return a;

}

//least common multiplier

function lcm(a,b){

return a*b/gcd(a,b)

}

function getLoopLength(arr{

var result = 1;

for(var i = 0;i<arr.length;i++)

result = lcm(result,arr[i])

return m

}

getLoopLength(lengths)

==> 120

// superimposing 4 rhythm with length 4,5,6 and 8 will result in a a rhythms that loops in 120 steps

Now I need a function that computes the minimum number of steps for the following hypotheses:

- The possible step lengths are bounded (between 2 and 11 in my case - might change)
- All the step lengths values must different
- 1 length value is known (will be a variable)
- The size of my lengths array can vary (between 1 and 4 in my case - will not change)

So what I'm after is a function that looks like this:

`var minPossibleLength(knownLength, lengthsSize){`

...

return min

}

For example minPossibleLength(4,4) should return 24 (when my lengths are [2,

Now I tried brute forcing it, loop through all possible lengths combinations and find the minimum lcm, and it does work with my conditions, but I'd love to know if I can find a more elegant and efficient solution.

Thx

Answer

The following algorithm for `minPossibleLength(4,4)`

finds better solution than 24: least common multiple for `[4, 2, 3, 6]`

is **12**.

```
var lengths = [4,5,6,8]
//greatest common denominator
function gcd(a,b){
var t,b,a
while(b != 0){
t = b;
b = a%b
a=t
}
return a;
}
//least common multiplier
function lcm(a,b){
return a*b/gcd(a,b)
}
function getLoopLength(arr, length){
var result = 1;
for(var i = 0;i<arr.length && i<length;i++)
result = lcm(result,arr[i])
return result
}
var minBound = 2;
var maxBound = 11;
function minPossibleLength(knownLength, lengthsSize) {
var min = 27720; // Maximum for bound range [2..11]
var newmin; // Newly computed minimum.
if (lengthsSize == 1)
return knownLength;
lengths[0] = knownLength;
for(var i = minBound; i<=maxBound; i++) {
if (i != knownLength) {
lengths[1] = i;
for(var j = (lengthsSize>2?i+1:maxBound); j<=maxBound; j++) {
if (lengthsSize<3 || (i != j && j!= knownLength)) {
lengths[2] = j;
for(var k = (lengthsSize>3?j+1:maxBound); k<=maxBound; k++) {
if (lengthsSize<4 || (i != k && j != k && k!= knownLength)) {
lengths[3] = k;
newmin = getLoopLength(lengths, lengthsSize)
if (newmin < min) {
min = newmin;
console.log('Minimum lcm so far for (['+knownLength+', '+i+(lengthsSize>2?', '+j+(lengthsSize>3?', '+k:''):'')+']) = '+min);
}
}
}
}
}
}
}
return min;
}
minPossibleLength(4,4);
```

Source (Stackoverflow)