Sunday, July 12, 2009

Puzzle 40 – Solution.

I like these optimization puzzles since it brings a variety of solutions and just shows how small changes to the algorithm could make a huge impact.

Here is the optimization that I had in mind. It makes the code run in less than 5 seconds on my machine. Throw in a couple of more optimizations like incrementing by 20 instead of 1 (see comments here) brings down the execution time to less than half a second!!

package com.sam.twisters.euler;
/* Problem 5 : Euler
* 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
* What is the smallest number that is evenly divisible (divisible without reminder) by all of the numbers from 1 to 20?

public class prog5 {
/*Simple function to check if the divisor completely divides the divident*/
public static boolean isDivisble(int divident, int divisor) {
if(divident%divisor == 0){
return true;
return false;

public static void main(String[] args)
long startTime = System.nanoTime();
boolean va = true;

/* Start looping though all the numbers and see if we can find one divisible by all numbers
* from 1 to 20.
int i = 1;
= true; //Assume that i is a valid answer to the puzzle
//Optimization -->for(int d=1;d<=20;d++){
(1 char, start from 11 and not 1).
This works since atleast one of the numbers from 11 to 20 has each of the numbers 1-10 as a factor,
so for example when we test if a number is divisble by 12 - we also indirectly test that the
number is divisible by 2,3,4 and 6
for(int d=11;d<=20;d++){
if (!isDivisble(i, d)){ //Yikes my assumption was wrong!
va = false;
//Optimization -->break; (6 char)
long estimatedTime = System.nanoTime() - startTime;

Best solutions for the week?

@TheMalkolm - I'll pick TheMalkolm solution - its a pretty good optimization to the existing code.

@Sebastian - Yep your second solution is pretty neat (took some time figuring out how it works!!) though as you pointed out it uses a completely different algorithm. Neat nonetheless!!

No comments:

Post a Comment

Solution for this question?