Updates from June, 2016 Toggle Comment Threads | Keyboard Shortcuts

  • loctv 6:00 pm on June 23, 2016 Permalink | Reply  

    Problem 5: Smallest multiple 

    *Difficulty: Easy

    Problem

    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 positive number that is evenly divisible by all of the numbers from 1 to 20?

    How to solve it:

    As you may know, if the number is divisible by all the numbers from 1 to 20, it must first divisible by 20. With this in mind, we can come up with a pretty fast and simple solution.
    Start from 20, check if the number’s divisibility , if it is, we stop and print out the result, if it not, we step forward 20 steps (as explained). This will dramatically decrease run time from hundreds of milliseconds to just a few dozens of milliseconds as we just step 1 step forward.

    Implementation (Java):

    public class Prob5 {

            public static void main(String[] args) {

                     long cur = System.currentTimeMillis();

                     long n = 20;

                    while(!checkDivisibility(n)) {

                              n+=20;

                    }

                    System.out.println(n);

                    System.out.println(“Took “ + (System.currentTimeMillis() cur) +” ms”);         

            }

            private static boolean checkDivisibility(long n) {

                   for(int i = 1; i <= 20; ++i)

                            if(n % i != 0) return false;

                                    return true;

                  }

    }

    Advertisements
     
  • loctv 5:17 pm on June 23, 2016 Permalink | Reply  

    Problem 4: Largest palindrome product 

    *Difficulty: Easy

    Problem:

    A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

    Find the largest palindrome made from the product of two 3-digit numbers.

    How to solve:

    For the shake of simplicity, I come up with an O(n^2) solution, check all possible solutions from 101 to 999 (inclusive)

    Solution took about 55 to 120 ms

    Implementation (Java):

    public class Prob4 {

            public static void main(String[] args) {

                    long cur = System.currentTimeMillis();

                    int max = Integer.MIN_VALUE;

                   for(int count1 = 100; count1 <= 998; ++count1) {

                           for(int count2 = count1+1; count2 <= 999; ++count2) {

                                   if(isPalindrome(String.valueOf(count1*count2)) && count1*count2 >                                   max) {

                                           max= count1*count2;

                                  }

                           }

                   }

                    System.out.println(max);

                    System.out.println(“Took “ + (System.currentTimeMillis() cur) + ” ms”);

           }

            private static boolean isPalindrome(String s) {

                    int length = s.length();

                    for(int count = 0; count < length/2; ++count) {

                            if(s.charAt(count) != s.charAt(length1count))

                                    returnfalse;

                            }

                    return true;

            }

    }

     
  • loctv 3:26 pm on June 23, 2016 Permalink | Reply  

    Problem 3: Largest prime factor 

    *Difficulty: Easy

    Problem:

    The prime factors of 13195 are 5, 7, 13 and 29.

    What is the largest prime factor of the number 600851475143 ?

    How to solve:

    There are many possible approaches,Pollard’s rho algorithmShanks’ square forms factorizationLenstra elliptic curve factorizationQuadratic sieveGeneral number field sieve to name a few. 

    My approach is using sieve Eratosthenes algorithm to create a prime numbers dictionary. As you may notice, we don’t need to calculate the prime numbers bigger than the square root of 600851475143 (google for more details) , which is 775146 . So the largest prime number in the dictionary will never exceed 800000 (I want to make sure everything is in the dictionary). We loop from 2 to 775146, check if that number is divisible by 600851475143 and is a prime number, if it is, check if it is bigger than max (which is initialized by -Infinity) . If the conditions are true, then assign i to max.

    (Or we can loop from 775146 to 2 , if the first number that divisible by 600851475143 is a prime number, then it has to be the biggest prime factor. This will save some assignment statements, but the amount of time it takes will be relatively equal with the above method)

    Implementation (Java):

    import java.math.BigDecimal;

    import java.util.Arrays;

    public class Prob3 {

            private static boolean[] sieveEratosthenes;

            privatestaticfinalintSIZE = 800000;

            public static void main(String[] args) {

            //using sieve Eratosthenes algorithm to create a prime numbers dictionary

            long cur = System.currentTimeMillis();

            sieveEratosthenes= new boolean[SIZE];

            Arrays.fill(sieveEratosthenes, true);

            for(int i = 2; i < sieveEratosthenes.length; ++i ){

                    if(sieveEratosthenes[i]) {

                            for(int j = 2*i; j < sieveEratosthenes.length; j+=i)

                            sieveEratosthenes[j] = false;

                    }

             }

             int limit = (int)Math.sqrt(600851475143l);

             long number = 600851475143l;

             for(int i = limit; i >=2 ; i) {

                     if(number%i==0 && isPrime(i)){

                              System.out.println(i);

                              System.out.println(“Took “ + (System.currentTimeMillis()cur) + “ms”);

                             break;

                     }

            }

            /*

             int max = Integer.MIN_VALUE;

             for(int i = limit; i >=2 ; –i) {

                        if(number%i==0 && isPrime(i)){

                                   if(i > max)

                                               max = i;

                       }

              }

            System.out.println(max);

            System.out.println(“Took ” + (System.currentTimeMillis()-cur) + “ms“);

            */

             }

              privatestaticbooleanisPrime(int n) {

                          return sieveEratosthenes[n];

              }

    }
    Solution took <50 ms

     
  • loctv 2:02 pm on June 23, 2016 Permalink | Reply  

    Problem 2: Even Fibonacci numbers 

    *Difficulty: Easy

    Problem

    Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

    1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

    By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

    How to solve:

    First, we create a variable type int (or long) to store the total value, this variable is initialized by 2 (2 is the smallest even-valued term). And two numbers, for example, name n1 and n2 , initialized with 1 and 2, respectively. Moreover, we need a variable represent the Fibonacci value, you can name it whatever you want, I call it fibo (for short). We loop until fibo is still <= 4 millions , add n1 and n2 , assign that value to fibo, then we assign n2 to n1, and fibo to n2.
    fibo = n1 + n2;

    n1 = n2;

    n2 = fibo;

    And then see if fibo is an even number , if it is, add fibo to sum

    sum += fibo;

    Implementation (Java):

    public class Prob2 {
    
            private static final intTHRESHOLD = 4000000;
    
            public static void main(String[] args) {
    
                   int n1 = 1;
    
                   int n2 = 2;
    
                   int fibo = 0;
    
                   //2 is the smallest even-valued term
    
                  int sum = 2;
    
                  long cur = System.currentTimeMillis();
    
                 do {
    
                         fibo= n1+n2;
    
                         n1 = n2;
    
                         n2= fibo;
    
                         if(fibo % 2 == 0) {
    
                                    sum+= fibo;
    
                         System.out.println(fibo);
    
                        }
    
               }while(fibo <= THRESHOLD);
    
               System.out.println(sum);
    
               System.out.println("Took " + (System.currentTimeMillis()-cur) + "ms");
    
         }
    
    }
    

    Solution took 0ms

     
  • loctv 1:37 pm on June 23, 2016 Permalink | Reply  

    Problem 1: Multiples of 3 and 5 

    *Difficulty: Easy

    • Problem:

    If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

    Find the sum of all the multiples of 3 or 5 below 1000.

    • How to solve:

    We can solve this problem by looping i from 3 (3 is the smallest multiples of 3) to 999 (below 1000), then check

    if (i mod 3 equals 0  or  i mod  5 equals 0)

    if the condition is true, then add i to sum (initialized with 0)

    • Implementation (Java):

    public class Prob1 {

    public static void main(String[] args) {

            int sum = 0;

            long cur = System.currentTimeMillis();

            for(int i = 3; i < 1000; ++i) {

                    if(i % 3 == 0 || i % 5 ==0) {

                    sum += i;

            }

            }

            System.out.println(sum);

            System.out.println(“Took “ + (System.currentTimeMillis()cur) + “ms”);

           }

    }

    Solution took 0ms

     

     
c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel