Problem 011 : Largest Product in a Grid

Largest product in a grid

Problem 11

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.
What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

                                                                                                       (https://projecteuler.net/problem=11)

Problem 11 can be done manually without complicated algorithms.

There will be four components in our calculation: horizontal —, vertical |, descending diagonal \ and ascending diagonal /.

First step is to store the numbers into 20 x 20 2-D arrays.

This can be done manually, or using file reader.

public static int[][] read()
{
 int[][] text = new int[20][20];
 File file = new File(text011);
 try (BufferedReader br = new BufferedReader(new FileReader(file)))
 {
  String line;
  for (int i=0; (line = br.readLine()) != null; i++)
  {
   String[] temp = line.split(" ");
   for (int j=0; j < 20; j++)
    text[i][j] = Integer.parseInt(temp[j]);
  }
 }
 catch (IOException e)
 {
  System.err.println(e);
 }
 return text;
}

After this, we will set the limit to 20 - 3, or 17.

The reason is that once we get to the column (or row) 17, we reached the maximum starting point since 17, 18, 19, 20 will form the last four-adjacent groups.

The remaining steps are to calculate the greatest sum using nested for-loops.

Horizontal will be increasing column by 0, 1, 2, 3:

h = grid[i][j] * grid[i][j+1] * grid[i][j+2] * grid[i][j+3];

Vertical will be increasing row by 0, 1, 2, 3:

v = grid[j][i] * grid[j+1][i] * grid[j+2][i] * grid[j+3][i];

Descending Diagonal will be increasing both row and column by 0, 1, 2, 3:

d1 = grid[i][j] * grid[i+1][j+1] * grid[i+2][j+2] * grid[i+3][j+3];

Ascending Diagonal will be decreasing column and increasing row at the same time by 1:

d2 = grid[i][j+3] * grid[i+1][j+2] * grid[i+2][j+1] * grid[i+3][j];

thus maintaining the sum of row and column as i + j + 3.

It was relatively easy problem, and there isn't any faster or fancier algorithm to solve it.


Answer is 70600674
Execution time is 3.771644 ms, or 0.003 seconds
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem011.java

Problem 010 : Summation of Primes

Summation of primes

Problem 10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

                                                                                                         https://projecteuler.net/problem=10

Problem 10 is about primality of integers.

There are two main ways to do this, but let's start with the one we already know.

First method is to use boolean isPrime(int n) to check each integer until we reach two million.

public static boolean isPrime(int n)
{
     if (n <= 3) return n > 1;
     else if (n % 2 == 0 || n % 3 == 0) return false;
     else
     {
      for (int i = 5, end = (int)Math.sqrt(n); i <= end; i += 6)
      {
       if (n % i == 0 || n % (i + 2) == 0) return false;
      }
     }
     return true;
}

Loop through each integer using for-loop and check their primality.

We get the answer in 603 ms. Pretty decent, but we are not really satisfied.


So here comes our new approach to this problem.

But before that, let's briefly talk about different ways to store integers in an array.

We will consider storing 1, 3, 5, 8 into an array.


First way is to directly store integers in an array.

index	0	1	2	3
value	1	3	5	8

Second way is to have a boolean array and stored number has true value in its index.

index	0	1	2	3	4	5	6	7	8
value	false	true	false	true	false	true	false	false	true

This array contains exactly same information as the first array.

Only index 1, 3, 5, 8 have true value, which means the "if array has that value" will be true.

The only difference is that the array size is usually larger than the number of integers we want to store.

However, it is phenomenally faster for finding certain integers in the array and adding/ removing certain integer.

Adding would be just changing that index to true, removing would be false.



Using this basic idea, we will now use the Sieve of Eratosthenes.

Sieve of Eratosthenes uses exactly same concept as the second example.

We will make a boolean array called isPrime, and isPrime[n] will return whether n is a prime or not.


The basic concept of the sieve is that "any multiple of prime number is not a prime."

Let's start with a table of numbers from 1 to 20.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

Now, by definition, 1 is not a prime. (as well as any integer less than or equal to 0)

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

We are on 2 right now. We started with 0, and until we came to 2, no number could cross out 2.

Therefore 2 is a prime number.

Because 2 is a prime number, any multiple of it (which will be rest of even integers) won't be prime.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

Now, we are on 3. Until we came to 3, no number could cross out 3.

Therefore 3 is a prime number.

Because 3 is a prime number, any multiple of it (6, 9, 12, 15, ...) won't be prime.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

Now we are on 4. Uh-oh, it's already crossed out. Until we came to 4, some number crossed out 4.

So 4 is not a prime, and we just go on to the next number.


We are on 5. Until we came to 5, no number could cross out 5.

Therefore 5 is a prime number.

Because 5 is a prime number, any multiple of it (5, 10, 15, ...) won't be prime.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

And we notice that no additional composite numbers were crossed out this time.

So we know our limit for checking the prime is up to the square root of the original limit.

For example, square root of 20 is 4.47, and 5 is above that limit, so we didn't need to check 5.

In other sieves, we will repeat the above process until we get to the square root of original limit.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

Notice that the uncrossed numbers are all prime numbers.

So if we convert this table into an array of boolean values,

the crossed-out index will have false value, while survived index will have true value.

And this information will be stored in isPrime array and we can just call array every time we need.

For example, if we want to check whether 9 is a prime number, then:

public static void main(String[] args)
{
    if (isPrime[9])
    {
        System.out.println("9 is a prime number.");
    }
    else System.out.println("9 is not a prime number."); // this will print
}

And here is the implementation for the sieve.

public static boolean[] primeList(int n)
{
        //sieve of Eratosthenes
        boolean[] prime = new boolean[n+1];
        Arrays.fill(prime, 2, prime.length, true);
        for (int i=4; i < prime.length; i+=2) prime[i] = false;
        for (int i=3, end = (int)Math.sqrt(n); i <= end; i+=2)
        {
         if (prime[i])
          for (int j=i*i; j <= n; j+=2*i)
           prime[j] = false;
        }
        return prime;
}

Answer is 142913828922
Execution time is 15 ms, or 0.015 seconds
Source code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem010.java

Problem 009 : Special Pythagorean Triplet

Special Pythagorean triplet

Problem 9

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

                                                                                                           https://projecteuler.net/problem=9

Problem 9 is about Pythagorean triplet.

The basic formula is :

A² + B² = C²

Using this formula will easily solve the problem.

One quick trick is to set the limit to int A and B so that we can reduce the time.

Assuming that B is always greater than or equal to A, B will always start with A.

Also, A will be less than one third of the perimeter since A is the smallest side of a triangle.

B will be less than one half of the perimeter since B should be smaller than the hypotenuse, C.

for (int a=1, end = 1000/3; a < end; a++)
{
 for (int b=a, end2 = 1000/2; b < end2; b++)
 {
  int c = 1000-a-b;
  if (c>0 && a*a + b*b == c*c)
  {
   System.out.println(a*b*c);
   return;
  }
 }
}

Answer is 31875000

Execution time is 1.7 ms, or 0.0017 seconds

Source code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem009.java

Problem 008 : Largest Product in a Series

Largest product in a series

Problem 8

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

                                                                                                           https://projecteuler.net/problem=8

Problem 8 is a simple problem if we know how to deal with string and char.

First, we store the series into a string.

private static final String NUM = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";

Then we will store each item into char array so that we attain an easy access to each value.

int[] digit = new int[NUM.length()];
for (int i=0; i < NUM.length(); i++)
 digit[i] = Character.digit(NUM.charAt(i), 10);

Now, we just need to use nested for-loop to find the greatest 13-adjacent product in the series.

long max = 0;
for (int i=0; i <= NUM.length()-LEN; i++)
{
 long temp = 1;
 for (int j=i; j < i+LEN; j++)
 {
  if (digit[j] == 0) break;
  temp *= digit[j];
 }
 if (temp > max) max = temp;
}
System.out.println(max);

Answer is 23514624000
Execution time is 1 ms, or 0.001 seconds
Source code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem008.java

Problem 007 : 10001st Prime

10001st prime

Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?

                                                                                                           https://projecteuler.net/problem=7
Problem 7 is about prime generation.

The efficiency of this problem can differ based on which algorithm we take.

We might want to use sieve for this problem, yet since we don't know the exact limit, we cannot use it (unless it will become more inefficient algorithm).

We will look at the algorithm that determines whether a number is a prime.

public static boolean isPrime(int n)
{
     if (n <= 3) return n > 1;
     else if (n % 2 == 0 || n % 3 == 0) return false;
     else
     {
      for (int i = 5, end = (int)Math.sqrt(n); i <= end; i += 6)
      {
       if (n % i == 0 || n % (i + 2) == 0) return false;
      }
     }
     return true;
}

This is by far the most efficient algorithm for checking primality of an integer.

We will use while loop until we reach our target, 10001st prime number.

Quick trick would be an increment of the integer by 2, since all even numbers cannot be prime.

Answer is 104743
Execution time is 8 ms, or 0.008 seconds
Source code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem007.java

Problem 006 : Sum Square Difference

Sum square difference

Problem 6

The sum of the squares of the first ten natural numbers is,

1² + 2² + ... + 10² = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

                                                                                                           https://projecteuler.net/problem=6

Problem 6 is a really simple problem if you know how to use for loop.

However, just like problem 1, I used formula to solve this problem, instead of for loop.

The formula for the sum of first n integers is:

n * (n + 1) / 2

The formula for the sum of first n squares is:

n * (n + 1) * (2n + 1) / 6

Therefore, the sum of the squares is:

int sumsquare = (NUM*(NUM+1)*(2*NUM+1))/6; //sum of the squares

and the square of the sum is:

int squaresum = (int)Math.pow((NUM)*(NUM+1)/2, 2);  //square of the sum

Answer is 25164150

Execution time is 0.8 ms, or 0.0008 seconds

Source code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem006.java

Problem 005 : Smallest Multiple

Smallest multiple

Problem 5

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?

                                                                                                           https://projecteuler.net/problem=5

Problem 5 is about GCD and LCM.

GCD : greatest common divisor

LCM : least common multiple

The problem already told us that 2520 is smallest number that is divisible by numbers from 1 to 10, or it is the LCM of numbers from 1 to 10.

Now we need to find LCM for 1 to 20.

Here is a simple math.

Let's say we have two integer, A and B.

And we know that G is the greatest common divisor of A and B.

Then we can write them in this way:

A = Ga

B = Gb

where a and b are relatively prime to each other.

Also, least common multiple must be divisible by both A and B but need to be as small as possible.

LCM = Gab

How do we get LCM directly from A and B?

LCM = Gab

Gab = G² ab / G = Ga * Gb / G = A * B / G

Therefore,

LCM = A * B / G

Here is recursive solution to find GCD for long a and long b:

public static long gcd(long a, long b)
{
    if (b == 0) return a;
    else return gcd(b, a%b);
}

The solution uses the Euclidean Algorithm for finding GCD:

Let's say there are two positive integer A, B A > B > 0

A = qB + R₀
B = qR₀ + R₁
R0 = qR₁ + R₂
…
R_N-1 = qR_N + 0

∴ GCD = R_N

and here is solution for LCM for integer for long a and long b:

public static long lcm(long a, long b)
{
    return a*b/gcd(a,b);
}

Answer is 232792560
Execution time is 2 ms, or 0.002 seconds
Source code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem005.java

Problem 004 : Largest palindrome product

Largest palindrome product

Problem 4

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.

                                                                                                           https://projecteuler.net/problem=4

Problem 4 is about palindrome number.

The term "palindrome" is applicable for words, numbers, and any phrases.

(i.e. "race car" can be reversed to "rac ecar" which reads "race car")

(i.e. "1234321" can be reversed to "1234321" which is same as before)

(i.e. the longest palindromic phrase known starts with "a man, a plan, a cameo, .."

       and ends with "...., a canal, Panama!")

When we reverse number, we can manually divide each digit and recreate a reversed number, but that way will take a long time to compute and therefore inefficient.

Instead, we can convert number into string and reverse string using StringBuffer.

The source code is right here below:

public static boolean isPalin(String n)
{
    return (new StringBuffer(n).reverse().toString().equals(n));
}

We now need to think about finding the largest product.

Our approach will take from the largest 3-digit integers, since that way we can reduce execution time a lot. Starting with i = 999, we will automatically stop when the next i is less than square root of the largest product found so far, since smaller i from that point will never produce larger product.

In the nested for loop, we will stop the loop when the product is less than the product found. Because we are reducing the value of j, further calculation is unnecessary for it will produce smaller product.

int ans = 0;
for (int i = 999; i >= Math.sqrt(ans); i--)
{
    for (int j = i; j >= 100; j--)
    {
        int temp = i*j;
        if (temp < ans) break;
        else if (isPalin(String.valueOf(temp))) ans = temp;
    }
}

Answer is 906609
Execution time is 6 ms, or 0.006 seconds
Source code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem004.java

Problem 003 : Largest Prime Factor

Largest prime factor

Problem 3

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

                                                                                                           https://projecteuler.net/problem=3

Problem 3 is about prime factorization.

Before we get into the problem, let's talk briefly about prime numbers and factorization.

(I will talk about prime numbers and primality more specifically in later problems.)

Here are some properties that we need to know:

1. Except for 2, all prime numbers are odd numbers.

2. When we divide a number, there is always a pair of divisors except for perfect squares.

    For example, if we look at divisors of 12 : 1, 2, 3, 4, 6, 12

    we can easily find three pairs (1, 12), (2, 6), (3, 4)

    and each pair will have a product of original number (which is 12 in this case).

    So we can conclude that if 12 is divisible by 1, then it is divisible by 12 for sure.

                                            if 12 is divisible by 2, then it is divisible by 6 for sure.

                                            if 12 is divisible by 3, then it is divisible by 4 for sure.

    We now divide them into two groups: smaller group (1, 2, 3) and larger group (4, 6, 12).

    And we see that the dividing borderline is between 3 and 4.

    This dividing borderline can be calculated by taking square root of 12, which is 3.4641

    Therefore, when we want to test divisibility, we just need to test divisors up to the square root of
    the original number, and we can raise efficiency by removing redundancy of calculation.

    One exception is when we have a perfect square, because the square root of perfect square is an

    integer, which cannot be a clear dividing borderline of divisors.

    For example, if we look at the divisors of 16: 1, 2, 4, 8, 16

    We get an odd number of divisors. Also, 4 can be either smaller or larger group.

    This is the reason that when we make an universal solutions for finding factors, we need to include
    square root of the number: from i = 2 up to i <= sqrt (original number)

In this problem, our number is 600851475143, which is neither an even number nor a perfect square.

Because it is not an even number, we don't need to divide it by 2. As stated above, all prime numbers other than 2 are odd, and we just need to test odd divisors; starting with i = 3, we can increment by 2 so that we can test just odd numbers (3, 5, 7, ...).

If we continue dividing a number by 3 (if it is divisible by 3) until it cannot be divided further, then the remnant is not multiple of 3 anymore. Do the same process for 5 and 7. When we reach divisor 9, it is not a prime factor since 9 is not a prime number. But we don't need to worry about it since we got rid of all the 3's from the number in earlier step. This is how we can do prime factorization without explicitly checking if the divisor itself is a prime number.

When we reach to the point where the number cannot be divided by any divisors smaller than its square root, then that remaining number would be the last number of our prime factorization, which is the answer to the problem.

public static void run()
{
    long d = 600851475143L;
 
    for (int i = 3; i < Math.sqrt(d); i+=2)
    {
         if (d%i == 0)
             while (d%i == 0) d /= i;
    }
    System.out.println(d);
}

Answer is 6857

Execution time is 2 ms, or 0.002 seconds

Source code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem003.java

I also made a universal solution for finding largest prime factor of a number in source code, so if you need any help about that, feel free to leave comment and ask questions.

public static int getLargestPrimeFactor(int n)
{

    if (n == 1) return 1; 
    if (n%2 == 0) while (n%2 == 0) n /= 2;
    if (n == 1) return 2;
  
    int i = 3;
    for ( ; i <= (int)Math.sqrt(n); i+=2)
    {
        if (n%i == 0)
             while (n%i == 0) n /= i;
    }
    i -= 2;
    if (n == 1) return i;
    return n;
}

Problem 002 : Even Fibonacci Numbers

Even Fibonacci numbers

Problem 2

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.

                                                                                                            https://projecteuler.net/problem=2

Problem 2 is about Fibonacci sequence.
Actual Fibonacci sequence starts with 1 and 1 (or, sometimes 0 and 1), but because the index of each term doesn't matter in this problem, we will not worry about that.

This problem is as simple as the first one, so I just want to briefly explain how I solved it.

I set the upper limit as four million as stated, and used while-loop (current term <= limit).
By using two integer f = 1 and s = 1, I started calculating the next term by adding the previous two terms and checked if it is even integer (current term % 2 == 0)

After adding even term to the sum, I assigned f = s and s = current term so that I can reuse the integers in next calculation until the term is greater than the limit, and we will reach the answer.

private static final int LIMIT = 4000000;
 
public static void run()
{
    int f = 1;
    int s = 1;
    int fibo = 0;
    int sum = 0;
    while (fibo <= LIMIT)
    {
        fibo = f + s;
        if (fibo%2 == 0) sum += fibo;
        f = s;
        s = fibo;
    }
    System.out.println(sum);
}

Answer is 4613732
Execution time is 0.8 ms, or 0.0008 seconds
Source code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem002.java