Smallest Common Multiple Bug? Code passes all tests locally, but fails last two on fCC

Smallest Common Multiple Bug? Code passes all tests locally, but fails last two on fCC
0.0 0

#1

Tell us what’s happening:
This code works just fine for all the fCC tests when run locally under Node.js or in Firefox/Chrome console.
Am I missing something here?

Your code so far

js

function smallestCommons(arr) {
  let lcm, largestNum, largestNumMultiple, remainders;

  // Create an array containing the range of numbers, from largest to smallest (inclusive) from the ones given in arr.
  let revRange = function(arr) {
    let rng = [];
    let rngLength = (Math.max(...arr) + 1) - Math.min(...arr);
    for (let i = 0; i < rngLength; i++) {
      rng.push(Math.max(...arr) - i);
    }
    return rng;
  }(arr);

  largestNum = revRange[0];
  largestNumMultiple = revRange[0];

  do {
    // Set remainders to an empty array at the loop outset.
    remainders = [];
    // Divide the current largestNumMultiple by each num in revRange, pushing the remainder of each result into 
    // the remainders array.
    for (let num of revRange) {
      remainders.push(largestNumMultiple % num);
    }
    // If every remainder of remainders === 0, the current largestNumMultiple is the least common multiple.
    if (remainders.every(remainder => remainder === 0)) {
      lcm = largestNumMultiple;
    }
    // Otherwise, add the original largestNum to the largestNumMultiple to create the next 
    // largestNumMultiple for the next loop.
    else {
      largestNumMultiple += largestNum;
    }
    // Keep running the loop while any remainder of remainders !== 0. Loop stops when every remainder === 0.
  } while (remainders.some(remainder => remainder !== 0));
  
  return lcm;
}


smallestCommons([1,5]);

Your browser information:

User Agent is: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.12; rv:60.0) Gecko/20100101 Firefox/60.0.

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


#2

I’m reasonably confident that your algorithm is correct but the tests are failing because it’s not “efficient” enough—the tests seem to just stop prematurely and fail silently (and returns undefined instead of throwing a meaningful error).

As an indication, the [1, 13] test case requires 27720 loops to calculate and the [18, 23] test case requires 263340. freeCodeCamp’s test runner seems to stop whenever it thinks it’s doing too much work; if you try to log the number of loops it’s actually not the same every time.

For now, I think you can give Chrome a try—it seems to be handling it a bit better than Firefox (at least for me, and I’m using the latest versions of both, I tried it with your algorithm and the [1, 13] test case passed. It looks like it’s browser and possibly even processor-dependent, so if it doesn’t work then the only way around it before it’s fixed is to write a more efficient algorithm.

Without changing too much of your code—you are currently creating and looping through the remainders array again and again, which, I think, is the most expansive part of your algorithm at the moment. Instead of of using an array to keep track of the remainders, I think it’s faster to do this:

let remainders = 0;

// ...

do {
  remainders = 0;

  // ...

  for (let num of revRange) {
    remainders += largestNumMultiple % num;

    // Terminate as soon as remainder is non-zero:
    if (remainders) {
      break;
    }
  }  

  if (!remainders) {
    lcm = largestNumMultiple;
  }
  else {
    // ...
  }
}
while  (remainders) {
  // ...
}

I can’t guarantee that will work—particularly if the number of loops (instead of run time) actually matters.

Alternatively, if you are keen on rewriting the whole thing, here is a hint:

Prime factors.

I hope that helps!

P.S. You may want to wrap your code with the [spoiler][/spoiler] tags since it’s a working solution.


#3

Ok, that makes sense about my algorithm being too inefficient. I tried your re-factorization and it passed all but the [18, 23] case on fCC in both Firefox and Chrome latest versions. Crap. Back to the drawing board, I guess. :\

I do know the algorithm itself works, though, and it seems to run slightly faster now under Node.js. How can we benchmark our algorithms to test their efficiency?


#4

Your code has been blurred out to avoid spoiling a full working solution for other campers who may not yet want to see a complete solution. In the future, if you post a full passing solution to a challenge and have questions about it, please surround it with [spoiler] and [/spoiler] tags on the line above and below your solution code.

Thank you.


#5

First off, don’t get me wrong, I am reasonably confident that your algorithm works, too, and I absolutely don’t think you did something “wrong” or “terrible”. In fact, I’m pretty sure that I’ve tried to solve a similar problem like this before, too. (I’m not saying that it’s okay because I did it, just… as a consolation/encouragement depending on how you read it d: ).

Coming back to your question, I think the best way to write efficient algorithms is through, learning and analysing common patterns, studying computer science (CS) and maths (I don’t have a background in computer science or maths), and practising by solving algorithm challenges/refactoring your code/analysing codebases/helping others. If you need to be convinced and you don’t know what a hash/lookup table is and how to use it—learn it before you continue with the rest of the challenges and you’ll know what I mean!

Benchmarking is a tricky JavaScript because it depends on engines and environments, if you want to go down the rabbit hole of “proper” benchmarking, I suggest reading YDKJS, Async & Performance, Chapter 6 to get a feel for it, which also includes a brief review on various tools (and caveats) that you can use to do proper benchmarking.

Disclaimer: below is a hand-wavy overview because there are just too many caveats you need to be aware of (more than happy to discuss further).

So… without going into the caveats, if you just want to get a rough comparison two different functions, I usually do:

Browser

fn() {
  // ...
}

let init  = performance.now();
let iterations = 1000;

for (let i = 0; i < iterations; i+= {
  fn();
}

let final = performance.now();
let average = (final - init) / iterations;

console.log(`${total} ms`});

Node.js

fn() {
  // ...
}

let init  = process.hrtime();
let iterations = 1000;

for (let i = 0; i < iterations; i+= {
  fn();
}

let final = process.hrtime(init);
let average = *final[0] * 1000 + final[1] / 1000000) / iterations;

console.log(`${total} ms`});

iterations is arbitrarily set based on personal needs (to minimise errors as much as is required). For Node.js I don’t think it’s too big of an issue because you get nanosecond resolution (I’m really not sure what the error on that is because I never looked into it, but judging from the repeatability, and reproducibility where a reference is used, it’s probably negligible compared to any algorithm that you want to test).

The bigger issue is when you do it in a browser environment, where time resolution of performance.now() is > 2 ms (it was increased substantially because of Spectre timing attacks), meaning that you need to run the function substantially many more times in order to get a small error.

What’s mentioned above is only valid when you compare different functions under the same environment, too, because Node.js and your browser (such as Firefox) may use different engines. In other words, you can’t say that because function A runs faster than function B in Node.js, it’s also the case in Firefox.

I hope that helps! :slight_smile:


#6

Sorry, I wasn’t aware of that. Thanks for correcting it. I just used the ‘Ask for help’ button which included the code by default in the post. I guess the saving grace was that it didn’t fully pass all of the tests on fCC as it was. Anyone who wants to view it can do so to see what not to do. LOL


#7

Haha… no problem. Hmm… maybe I’ll save the rabbit-hole for when I get a little more coding time under my belt. Thanks for the encouragement. :slight_smile:


#8

Ok, so… I went back to the drawing board and got a passing solution using the hint from @honmanyau. I stumbled upon some code from elsewhere for part of my solution and modified it for my purposes. It kinda felt like cheating a little, but I gave proper credit in my comments and made sure I understood exactly what it was doing before I used it. I’m sure it could be organized better, but it works, passes all tests, and is certainly faster now:

function smallestCommons(arr) {
  let lcmPrimes = {};

  /** Create an array containing the range of numbers, from largest to smallest (inclusive) from the ones 
   * given in arr. 
  */
  let revRange = function(array) {
    let range = [];
    let rangeLength = (Math.max(...array) + 1) - Math.min(...array);
    for (let i = 0; i < rangeLength; i++) {
      range.push(Math.max(...array) - i);
    }
    return range;
  }(arr);

  let getLCM = function(obj) { 
    let lcm = 1;
    for (let key in obj) {
      lcm *= Math.pow(Number(key), obj[key].exp);
    }
    return lcm;
  }

  for (let num of revRange) {
    /** H/T: James O'Reilly https://jsfiddle.net/JamesOR/RC7SY/ for the prime factorization idea */
    for (let i = 2; i <= num; i++) {
      // Initially set cnt for each iteration.
      let cnt = 0;

      /** Here, we only need the cnt of how many factors there are of 
       * value i. cnt for this iteration will be used as the exponent 
       * for the i's that pass the while test. The others are cnt = 0, and 
       * simply won't 'count' later.
       */
      while ((num % i) === 0) {
        cnt++;
        // factors.push(i);
        // Look, Mom, a virtual factor tree!
        num /= i;
      }
      
      /** Check the lcmPrimes object, which is initially empty. If there is no key value of i  
       * in it, add it and set the value to reflect the exponent as cnt for that i. Any iterations 
       * that still have cnt === 0 at this point aren't 'counted' here.
      */
      if (cnt && !lcmPrimes[i]) {
        lcmPrimes[i] = {'exp': cnt};
      }

      /** Here, a key of value i does exist. If the value of its property, exp, is less than cnt, 
       * update it to reflect the higher cnt as the new exponent (for lcm, we only want to keep the 
       * highest exponent of each factor). Again, any iterations that still have cnt === 0 at this 
       * point aren't 'counted' here.
        */
      else if (cnt && (lcmPrimes[i].exp < cnt) ) {
        lcmPrimes[i].exp = cnt;
      }
    }
  }

  return getLCM(lcmPrimes);
}

#9

Glad you found a way to pass the challenge, but it is really not necessary to post your solution (even though you blurred it out).


#10

Man, I can’t win for losin’ here… haha. I just wanted someone to see it and maybe get some feedback. Heck, I was pretty proud of it, myself, after having to re-do it. :slight_smile: