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;
     }
     else{
         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;
     do{
         va = 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)
                    break;
             }
         }
         i++;
     }while(!va);
     System.out.println(i);
     long estimatedTime = System.nanoTime() - startTime;
     System.out.println((float)estimatedTime/1000000000);
 }
}

http://www.blogtrog.com/code.aspx?id=7617cc6e-c724-4122-b5c5-bf6eb703a700

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!!