Smallest Common Multiple My code works perfectly at console but doesn't pass the tests, what's the problem?

Smallest Common Multiple My code works perfectly at console but doesn't pass the tests, what's the problem?
0

#1

Tell us what’s happening:

If you tested this at js fiddle or any console then you will see that it works perfectly but it doesn’t pass all the tests here, it doesn’t pass the last two tests. What’s wrong? Is it because it takes more time or something like that?

Your code so far


function smallestCommons(arr) {
  for(var i = Math.min(...arr)+1;i < Math.max(...arr);i++) {
    arr.push(i);
    arr.sort((a,b) => a - b);
  }
  var j = 1;
  while(true) {
    if(arr.every(element => j % element === 0) === true) {
      return j;
    }
    j++;
  }
}


smallestCommons([1,5]);

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:61.0) Gecko/20100101 Firefox/61.0.

Link to the challenge:
https://learn.freecodecamp.org/javascript-algorithms-and-data-structures/intermediate-algorithm-scripting/smallest-common-multiple/


#2

Guys? Help here please?


Smallest Common Multiple - help, I'm stuck!
#3

I’m not a math, js expert. but I believe your code doesn’t follow a good and logical algorithm.

First is about sorting out your array in for loop. You Should not sort the array every iteration, and you may sort it once you pushed elements on it(after for loop).

Second issue could be about you j++. (again I’m not mathpants), but I think it’s redundant to check range of min to max(exclusive) where max is the largest number in your array(check condition), considering following example:
you go for [1,6], here min is 1 and max is 6
Your while, you start it from 1, and check if it’s okay 1%elems_on_arr which fails becasue of 2.
Then you add 1 to j, now j is 2, but next iteration will fail becasue of 3 this time
Then you add 1 to j, now j is 3, but next iteration will fail becasue of 4 this time
The above logic till maximum number of your array.

So it’s better start from maximum number of array, and not add one by one, instead add it by max value.

var j = Math.max(...arr);
...
j+=Math.max(...arr);

Beside that I still think adding maximum value to current value and try again is not logical, becasue consider 17 and 18, it starts from J=18, J%17 is 17, so here adding another 18(max) to J and try again is nonsense, becasue for next 17 iteration it will not J%17===0.

Another thing could be about dividable small elements to larger elements. For example when your array has 2,3,4,…,8, and you add max(8) to each iteration, you should not check for 2, and 4, since they are divisible to 8, Same about 3 becasue you have 6.
So this is better check array elements divisibility to max value before you go for checking process.
Same checking the the result with max value is redundant, since you add 8 at each iteration, so it will always true.

About the math, you should ask some math expert, but indeed if I got some stuff in my mind about it, will help of course.

Same about js, if you just add one console.log("no way") after your while(true){} block you realized for the one failed test ([23, 18]) this line is triggered which is not expected! I’m not js expert, but I think browser may ignore the while since it’s too much already(exceeded process) and just ignores the rest of the while.

You should come up with better algorithm, to make it lighter, so your while loop never get ignored, and result the correct value.

I hope I could come up with the solution. The only thing I know is it’s easy becasue I can understand it, but should come up with the solution(sorry lack of math stuffs)

For now I suggest you apply the optimization and logical changes I stated.

Keep going on great work, happy programming.


#4

Thank you for the help.

I applied what you said(except the last one about divisibility) and it worked but there are still 1 test more.

But respectfully, your talking about ignoring the code doesn’t make that much of sense to me.

Consider this code:


function smallestCommons(arr) {
  // Sort array from greater to lowest
  // This line of code was from Adam Doyle (http://github.com/Adoyle2014)
  arr.sort(function(a, b) {
    return b - a;
  });

  // Create new array and add all values from greater to smaller from the
  // original array.
  var newArr = <a href='https://forum.freecodecamp.com/images/emoji/emoji_one/rocket.png?v=3 ":rocket:"' target='_blank' rel='nofollow'>];
  for (var i = arr[0]; i >= arr[1]; i--) {
    newArr.push(i);
  }

  // Variables needed declared outside the loops.
  var quot = 0;
  var loop = 1;
  var n;

  // 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++) {
      if (quot % newArr[n] !== 0) {
        break;
      }
    }

    loop++;
  } while (n !== newArr.length);

  return quot;
}

// test here
smallestCommons([1,5]);

As you see, the first code(.sort() method) is already a loop that sorts all the array elements, and the second code is a loop to add the difference between min to max that can take too long, and the third code is a loop INSIDE a loop, that’s technically more than 5 loops and let’s not mention how the variable quot calculates in every loop.

If that code passes the tests and mine doesn’t then there is definitely a problem but not by browser. Also if the browser ignores too much code running, then it wouldn’t run an infinite loop, wouldn’t it?

I can use other algorithm but it can take too long and as you see, a recommanded code that is from the lesson already uses 4 loops and some calculating.


#5

Besides, when I run the code in the console. It runs instantly(with a little delay)

So I don’t think that the problem is the code running time.


#6

Help please? …


#7

Aside from your code, this challenge is known to break in most browser if you brute force it. I don’t know the exact reason, but browser will shut down or apply break when it detects too many iteration. If you are not passing the last test case, this is likely be the reason.


Smallest Common Multiple - help, I'm stuck!
#8

So what I do now? Create a new whole “lite” algorithm or just ignore it?

Because from all algorithm I think about this challenge, doesn’t seem that there are any lite algorithms, there are an algorithm that uses Greatest Common Divisor but that requires a new whole function and it still uses some loops.


#9

Yep, use that if you want to pass the challenge. Computing GCD doesn’t need brute forcing (there is fast algorithm for it), so it will involve much less iteration. I actually haven’t tried it though. I’m probably gonna try it now as I’ve mentioned it.


#10

I think that I will just ignore the challenge. As long as the code works and as long as I’m (kinda) capable of doing this challenge myself, I don’t need freecodecamp points or stuff like that. I don’t need to complicate it until I reach O(n)

Anyway, thank you both @gunhoo93 and @NULL_dev for help. I still don’t know why the recommanded codes pass the tests while mine doesn’t but I think as long as it works(besides freecodecamp) without help then it doesn’t matter. Thank you again!


#11

If you are still curious here is the code that will pass the test

// Assume no error handling globally

// Assume a >= b
let gcd = (a, b) => {
  for (let tmp; b !== 0; ) {
    tmp = a
    a = b
    b = tmp % b
  }
  return a
}

// Assume a >= b
let lcm = (a, b) => a * b / gcd(a, b)

// Assume a <= b
let range = (a, b) => {
  let res = []
  for (; a <= b; ++a) {
    res.push(a)
  }
  return res
}

function smallestCommons(arr) {
  let args = (arr[0] < arr[1]) ?
    range(arr[0], arr[1]) : range(arr[1], arr[0])

  return args.reduce(lcm)
}

smallestCommons([23, 18])

#12

No! You are not running a native code. Browser may decide to ignore your heavy process whatever it thinks it’s eating resources(memory, CPU) so much.

If you think I’, wrong, just put a console.log(“not expected”); after your while(true){} loop. So what does while(true) mean? it means forever. And you just return something when you reach it, and there is no break.

Now if you check your code several times you see for heavy works(last test you mentioned) browser ignore the while true and breaks it, so this is becasue you get into the log. (@gunhoo93 is right, mentioned it right)


#13

I never said that you’re wrong. My question was why infinite loop happen? if the browsers ignore heavy processes then the browser should ignore infinite loop but it doesn’t(it doesn’t run too many recursion though because of stack overflow)

Also, why the recommanded code passes the tests when it runs many loops(there are even 1 loop inside a while loop, that’s supposed to be O(n), no?)? I’m confused. I’m sorry if you felt that I was trying to say that you’re wrong. I’m just curious and I want to learn.


#14

#1 What recommended code are you talking about?

#2 In general, nested loop is O(n^2) and loop is O(n). But they don’t have to be. For example many recursive algorithms can be made iterative, i.e) you use while or for loop. In that case, the running time is often O(lg(n)) despite the presence of a loop. Regardless, this is just a general guideline, you actually need to do rough analysis to know the rough running time of you algorithm.

#3 It may not be the browser, but the coding environment that is slicing the loop.


#15

I mean the recommanded solutions here: https://guide.freecodecamp.org/certifications/javascript-algorithms-and-data-structures/intermediate-algorithm-scripting/smallest-common-multiple

If what you said is right about O(n2) then that guy not only used O(n) but used O(n2) too, how that is not heavy process on the browser. I’m confused.


#16

I’m more leaned towards thinking that FCC coding environment is the problem (whatever that environment is).

Yours even on larger input, shouldn’t sweat any browser. If it did, many client heavy web apps will easily break.
As a proof of concept, if you copy and paste your code directly into a browser console and run the last test case, it will give correct result. But, I can’t pin down the exact reason why this happens exclusively to FCC or some other platform.


#17

It’s okay pal, don’t overthink about stuffs, surely I’m not the one know everything, as I mentioned I’m not good at math, so I can make mistakes of course. Take it easy pal. :smiley::+1:

put console.log("Loop: "+loop); after the do{}while(...) in that code, and see how many times that do-while iterated to find the answer.
Same have the same log to see how many times your code iterated to find the result. Go for a small amount [2,10] and try.

Your code,

var j = 1;
  while(true) {
    if(arr.every(element => j % element === 0) === true) {
      return j;
    }
    j++;
  }

I again repeat my sentence, adding one to the j and try it again for the array is not optimized, check my first answer again with given samples. your while has too much redundant iteration and process.

For [18,23], your loop should iterate over 6056820 times to find the answer, while optimized(suggested loop) just need 11971. If you follow my math stuffs, that 6056820 could be 216315(6056820/23), and as optimized code it’s less.

This is not about infinity loop, this is becasue when browser thinks too many resources are used for a function/code, it decides to ignore it. This is fair.

Now the optimized(suggested code you mentioned dear) has better code(algorithm, I still believe it could be faster by avoiding covered numbers as explained), so faster and has more luck to not ignored and any error, while your code doesn’t. That’s it all about.

You got it right, but it’s not optimized, that’s all. And for some reason, it may fail for heavy loads. I could not pass the test with your code for last test becasue browser just break the while after some notable iteration, that’s it pal.

Keep going on great work mate, happy coding.


#18

True and false. As I checked the @OGTechnoBoy code for [18,23] several times and counted to iterations browser could do before the break of while loop, they are completely different! So this could depend of system too, My system could not last for last test, and it’s expected.

Same true and false pal, I don’t know, but the context of the page script is loaded could affect the script load too. Let say the exact code could work with a empty page(low size context), and fail with FCC. it depends on browser implementation I believe.

The truth is(as expected, fair and logical) excessive heavy js code(ops per seconds we assume) could be ignored by browser.

Thanks for helping out mate, keep going on great work, happy programming.


#19

Well, now I really don’t know. Regardless, it’s kind of surprising how browser can’t handle this. Thanks.


#20

If browser let any code works what every it is and how much it needs resources, your browser and mine are doing bunch of bitcoin mining for others for instance.

JS should not be very heavy, that algorithm is not a client-side thing. It’s good to know how does an algorithm work, but you may not do heavy/complex math stuffs with JS.