Skip to main content

Project Euler Problem 1,2,3,4,5 in Java


NOTE : Don't look at the solution if you had not tried it yourself. Because real learning is an active process and seeing how it is done is a long way from experiencing that epiphany of discovery.So you try possible solution but something doesn't work and it's hours now when that could be done in minutes. There is nothing wrong in looking at the solution if you have been doing it for long and couldn't figure it out. After looking the solution you may realize what bit of changes you could do for better result. It might be something very silly or stupid thing that you forgot and it's very frustrating.No matter how frustrating problems are, there is almost certainly a solution out there on web. These are my attempts or solution to the problems it might be simple or complex depending on how well you understand my algorithm. I have solved each problem using Java. It took me less than hour in some problems to design efficient  and successful algorithm to meet the "One-minute rule" of Euler.


1) Problem 1 - Project Euler

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.

One possible solution: 

 public class main {
    /***
     * @Euler project 1

     * @Sum of all multiple of 3 and 5 below 1000
     * @Niraj Patel
     */

    public static void main(String[] args) {
        int sum=0;
        for(int i=1;i<1000;i++){
            if(i%3==0 || i%5==0){
                sum+=i;
            }       
        }
        System.out.println(sum);
    }
}



2) Problem 2 - Project Euler

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.

One possible solution:

public class main {
    /**
     * @Euler problem 2

     * @Sum of the even Fibonacci terms
     * @author Niraj patel
     */

    public static void main(String[] args) {
        int fib1 = 1,fib2 = 1,newFib = 2,sum = 0;
        while(newFib < 4000000){
            if(newFib % 2 == 0){
                sum += newFib;
            }
            fib1 = fib2;
            fib2 = newFib;
            newFib = fib1 + fib2; //Fibonacci sequence is generated by adding the previous two terms.
        } System.out.println("Sum = " + sum);
    }
}

3) Problem 3 - Project Euler

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
One possible solution:  

public class main {


/**
 * @Euler Project 3
 * @Largest
prime factor of 600851475143 
 * @Niraj Patel
 */

    public static void main(String[] args) {
        long num = 600851475143L;
        long newnum = num;
        long largestFactor = 0;
        int counter = 2;
        // counter * counter : To improve the algorithm,  Fundamental Theorem of Arithmetic (Logical explanation can be found on web).
        while (counter * counter <= newnum) {
            if (newnum % counter == 0) {
                newnum = newnum / counter;
                largestFactor = counter;
            } else {
                counter++;
            }
        }
        if (newnum > largestFactor) {
            largestFactor = newnum;
        }
        System.out.println(largestFactor);
    }
}


4) Problem 4 - Project Euler

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.

One possible solution: 

import java.util.ArrayList;
import java.util.Collections;

public class main {
/**
 * @Euler Project 4
 * @Largest palindrome of three digit
 * @Niraj Patel
 */
    static int number=0,reversnum = 0,reminder,original;
    public static void main(String[] args) {
       
        ArrayList<Integer> list = new ArrayList();
        for(int i=100;i<=999;i++){
            for(int j=100;j<=999;j++){
                number = i*j;
                original=number;
                //algorithm for palindrome number
                while(number>0){
                    reminder = number%10;
                    reversnum = reversnum*10+reminder;
                    number= number/10;
                }
                if(reversnum==original){
                    list.add(original);
                }
                original=0;
                reversnum=0;
            }
        }
        System.out.println(Collections.max(list));// To get maximum number from the list

    }
}
 

5) Problem 5 - Project 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 positive number that is evenly divisible by all of the numbers from 1 to 20?
one possible solution: 
 This one is little dirty but I think it is the simplest and quickest possible solution.
public class main {


/**
 * @Euler Project 5
 * @
Smallest evenly divisible number by all 1 to 20.
  * @Niraj Patel
 */

    public static void main(String[] args) {
        int number = 1000; // Obviously there is no number less than 1000 evenly divisible by all 1 to 20.
        while (!(number % 20 == 0 && number % 19 == 0 && number % 18 ==0
                &&number % 17 == 0 && number % 16 == 0 && number % 15 ==0
                &&number % 14 == 0 && number % 13 == 0 && number %12==0    &&number % 11 == 0)) {
            number += 20; //Increment by 20
        }
        System.out.println("The number that is evenly divisible by all of the numbers from 1 to 20: " + number);
    }
}

Comments

Popular posts from this blog

Non-decreasing Array - LeetCode

Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n). Example 1: Input: [4,2,3] Output: True Explanation: You could modify the first 4 to 1 to get a non-decreasing array.   Example 2: Input: [4,2,1] Output: False Explanation: You can't get a non-decreasing array by modify at most one element. Note: The n belongs to [1, 10,000]. Source: LeetCode At first glance, it looks like an easy and straightforward problem, but believe me it's greedy problem. In the problem, you are allowed to make atmost "one" modification to make a non-decreasing array. Nondecreasing means that every element is greater than or equal to the one before it e.g. [1,3,4,4,5,6,9]. For example, [2,2,3,2,4] can this become non-decreasing? Yes, by replacing 3 with 2 =>[2,2,2,2,4]. What about this:...

RLE Encoding and Decoding in C++

Given an input string, write a regular recursive function that returns the decoded (uncompresseed form) Run Length Encoded   (is a simple form of data compression where repeated character are replaced by count followed by the character repeated) string for the input string. Below are some examples: decode("*") =>* decode("3+") =>+++ decode("11*") =>*********** decode("101+") =>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ decode("abcde10+10*10+10x") =>abcde++++++++++**********++++++++++xxxxxxxxxx decode("\\") =>\ decode("\1\2\3") =>123 decode("13\7x") =>7777777777777x decode("5\\") =>\\\\\ decode("4\12\23\3") =>111122333 decode("4\\2\3") =>\\\\33 NOTE: To represent a single backslash, it’s necessary to place double backslashes (\\) in the input string to obtain the desired in...

Merge Two Binary Trees

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree. Example 1: Input: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7    Output: Merged tree: 3 / \ 4 5 / \ \ 5 4 7   Note: The merging process must start from the root nodes of both trees.  Source: LeetCode Solution: We traverse both trees in a p...