Effecient Algorithm for Small Common Multiple challenge

Effecient Algorithm for Small Common Multiple challenge
0

#1

I just finished the Small Common Multiple challenge, but I don’t think my choice of algorithm was the best. I’d like to know how others approached this one.

I’ve been doing a lot of study into functional programming recently and I decided that I wanted to try to solve this one with a purely functional approach. To this end, the table method listed here seemed like a good choice, but it hasn’t worked out so well.

The first version of my submission had several recursive helper functions and worked fine for smaller values, but I quickly ran into stack overflow errors (I blame JavaScript’s lack of tail recursion optimisation, my code was fine), so I had to redesign the main looping function as a while() loop. Even here there was a problem as then the site complained about an infinite loop. Investigating this, I discovered that number of iterations of while() loop using the table algorithm escalates quickly. With the input value of [1, 11] the loop clocks up a “mere” 21,969 iterations, but this jumps to a whopping 291,239 iterations at [1, 13], an eye-watering 10,040,399 for [1, 17] and I’m still waiting for [1,19] to finish. I’m now thinking that my choice of algorithm may not have been the best.

I’ve passed the test, the code works, but that seems to be a dreadfully ineffecient algorithm. I’d like to know how other people approached this problem and what algorithm they choose. Did you run into the same problems, or is there a better way of solving this one?


#2

I declared a (non-recursive) function lcm(a, b) that computes the least common multiple of two numbers. Then I declared a function expand(arr) that accepts an array of two numbers and returns an array of all numbers with the numbers from arr as endpoints (so expand([1, 5]) yields [1, 2, 3, 4, 5]). Then using the lcm function, I used reduce() on the result of the expand function. It essentially looks like this:

function expand(arr) {...}

function lcm(a, b) {...}

function smallestCommons(arr) {
  var nums = expand(arr);
  return nums.reduce(lcm);
}

This depends on the fact(?) that the lcm of, let’s say, 3 numbers a, b, and c is the same as the lcm of a and b, and the result of that lcm and c (or that lcm(a, b, c) is the same as lcm(lcm(a, b), c)). However I don’t have any proof of this property of lcm’s. I just assumed it to be true.


#3

Calculating the least common multiple was a one-liner for me. I used euclid’s algorithm to calculate the greatest common divisor (also a one-liner in fp-style) and calculated the lcm with that (as shown on the wikipedia article you linked). Finding the lcm of more than two numbers is done by folding/reducing: http://stackoverflow.com/a/147523.


#4

Here is my solution. I thought it was pretty efficient. As you can see, I did a while loop too, but with nested for loop.

function smallestCommons(arr) {
  var LCM, mult = 1, check = false
  
  arr.sort()
  
  while(!check){
    mult++; check = true; LCM = arr[1] * mult
    for(var i = arr[0]; i < arr[1]; i++) if(LCM % i) check = false
  }  
  return LCM
}

#6

Actually I did get one thing right. Building the initial array from the start and end parameters can be reduced to a single line:

  var inputArr = new Array (end-start+1).fill().map(
      function (_, index) { return (index + start);});

The new keyword, creates a new array of a given size, fill() assigns it with values, while map creates the values to fill it with. This also has the benefit of being side-effect free as far as I can tell, and no need for looping push() statements.


#7

OK, I just re-wrote this using a recursive gcd helper function and a reduce() construct for lcm calculation and it worked. smallestCommons ([1, 19]) is practically instantaneous now.

Thanks for your help guys.


#8

Keep in mind that making code shorter this way is not always more efficient (chaining usually isn’t) and is often much harder to read and maintain.


#9

Little late, here, but I also was able to solve this problem without using arrays. Not that I don’t like arrays, it just seems pointless to hold onto data when we’re just trying to compute a number. Anyway, this uses a while loop and I did have to put //noprotect so that the fCC checker would run the code (it passed). I feel that this algorithm challenge makes the coder operate on many assumptions: the ceiling and floor of the range, the lcm will be within javascript’s capabilities, that only two elements are given in the array. I’m probably getting ahead of myself concerning error handling, but here it is nonetheless. (Yes, its very much like @ChadKreutzer’s solution. I want to check out the euclid one as well.) Feedback welcomed, please :slight_smile:

   function smallestCommons(arr) {

	// Can't assume that the array given is ascending order
	if (arr[0] > arr[1])
		arr = arr.reverse();

	// Start testing at largest number in range
	var test = arr[1], foundIt = false;

	while (!foundIt) {
		foundIt = isMultiple(arr[0], arr[1], test);
		test++;
	}

	return test - 1;
}

function isMultiple(x, y, test) {
	for (var i = x; i <= y; i++) {
		if (test % i !== 0)
			return false;
	}
	return true;
}


console.log(smallestCommons([1, 5]));

#10

How do you make it so efficient? I have a hard time properly visualizing the whole picture. Is there any particular exercises to practice the brain?


#11

@skratchbreaker A first step in improving efficiency is to identify unnecessary operations. Walk through your algorithm and work out each step by hand, using pen and paper. Are you running calculations on values you’re not going to use? Are you performing operations on the same values more than once? Are there any opportunities to escape a code block early?

For the curious, below is one way to solve the challenge without turning loop protect off:

function smallestCommons(arr) {
  var smallest = Math.min(arr[0],arr[1]);
  var biggest = Math.max(arr[0],arr[1]);
  var least = lcm(smallest, smallest+1);
  if (biggest - smallest === 1){
    return least;
  } else {
    return lcm(least, smallestCommons([smallest+1, biggest]));
  }
}

function lcm(a,b) {
  return Math.abs(a*b)/gcd(a,b);
}

function gcd(a,b) {
  if (b === 0){
    return a;
  } else {
    a = a-b*(Math.floor(a/b));
    return gcd(b,a);
  }
}

#12

How do you obscure code like that?


#13

[spoiler]code[/spoiler]


#14

Thanks! Is that typical Github Markdown or just something for this tool?


#15

It’s specific to the forum.