CODEWITHSUNDEEP
javascriptarraysalgorithmmath
Boy pro
Boy pro

Reputation: 462

Is my algorithm wrong or it's right and just needs tweaks?

<html><head></head>
<body><script>
  function GCD(a, b) {
    if (a == 0) {
      return b;
    }
    return GCD(b % a, a);
  }

  function difference(array) {
    for (var i = Math.min(...array) + 1; i < Math.max(...array); i++) {
      array.push(i);
    }
    array.sort((a, b) => a - b);
  }

  function smallestCommons(arr) {
    difference(arr);
    console.log(arr);
    a = arr[arr.length - 1];
    b = arr[arr.length - 2];
    var LCM = a * b / GCD(a, b);
    while (true) {
      var index = arr.findIndex(element => LCM % element !== 0);
      if (index === -1) {
        return LCM;
      }
      LCM *= arr[index];
      console.log(LCM);
    }
  }
  smallestCommons([1, 5]) // right 
  smallestCommons([2, 10]) // right
  smallestCommons([1, 13]) // wrong
  smallestCommons([23, 18]) // wrong
</script></body>
</html>

This is a code for this challlenge: https://learn.freecodecamp.org/javascript-algorithms-and-data-structures/intermediate-algorithm-scripting/smallest-common-multiple/

The algorithm I use:

1-Calculate LCM of the two greatest numbers.

2- Try LCM % number on all the array and if you find a number that doesn’t return 0, assign it to the var index and multiply it * LCM then keep doing like that until it doesn’t find anything and returns -1 instead, when that happens, return LCM finally.

The code works at the first two arrays but it doesn’t work at last two which caused me to think, is my algorithm wrong and I’m just wasting my time trying to tweak it or it’s right and it just needs some tweaks?

Notice that there are 3 different functions, the first function calculates GCD to calculate LCM later, then the second function pushes the values between the two values in the array and then sorts it, and the third function calculates LCM(Lowest Common Multiple)

The problem is that the last second arrays:

smallestCommons([1, 13]) returns 4324320 instead of 360360

smallestCommons([23, 18]) returns 72681840 instead of 6056820

So what I want to know, please focus on this:

Is my whole way(algorithm) wrong and I need to rewrite a whole one or it needs some tweaks to work?

Please, don't give me ready codes. Just tell me what I want to know and thank you (:

Upvotes: 4

Views: 125

Answers (1)

jaboja
jaboja

Reputation: 2237

You are wrong multiplying by arr[index].

Let relabel our variables for clarity:

    N = array[index]
    p = GCD(LCM, N)

now we can rewrite N and LCD as:

    N = p × q
    LCM = p × r

to have the smallest number being lowest common multiple of current LCM and N you need to calculate it as:

    LCM := p × q × r

But if you calculate it with code

LCM *= arr[index];

you in fact calculate

    LCM := (p × r) × (p × q) = p × p × q × r

i.e. one p factor too much. To calculate it as needed you should use following code instead:

LCM *= arr[index] / GCD(LCM, arr[index]);

Upvotes: 1

Related Questions