How to Solve the First 100 Project Euler Problems 11-15

pe -11-15

if you’re new here start with part 1. Welcome to the third part of the “Solve Project Euler Problems” series where we will tackle some excellent math and programming challenges. You don’t need to be a genius; all you need is curiosity and a love for problem-solving. Let’s dive in!

Problem 11: Largest Product in a Grid

Understanding

You’re given a 20×20 grid of numbers. Your task is to find the greatest product of four adjacent numbers in any direction: up, down, left, right, or diagonally.

Brute-Force Logic

Loop through the grid, calculating the product of four adjacent numbers in each of the possible directions. Keep track of the largest product.

Python and JavaScript Implementations

Python:

def largest_grid_product(grid):
    max_product = 0
    rows, cols = len(grid), len(grid[0])
    for i in range(rows):
        for j in range(cols):
            # Horizontal
            if j <= cols - 4:
                max_product = max(max_product, grid[i][j] * grid[i][j + 1] * grid[i][j + 2] * grid[i][j + 3])
            # Vertical
            if i <= rows - 4:
                max_product = max(max_product, grid[i][j] * grid[i + 1][j] * grid[i + 2][j] * grid[i + 3][j])
            # Diagonal (left to right)
            if i <= rows - 4 and j <= cols - 4:
                max_product = max(max_product, grid[i][j] * grid[i + 1][j + 1] * grid[i + 2][j + 2] * grid[i + 3][j + 3])
            # Diagonal (right to left)
            if i >= 3 and j <= cols - 4:
                max_product = max(max_product, grid[i][j] * grid[i - 1][j + 1] * grid[i - 2][j + 2] * grid[i - 3][j + 3])
    return max_product

JavaScript:

function largestGridProduct(grid) {
    let maxProduct = 0;
    const rows = grid.length;
    const cols = grid[0].length;
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            // Horizontal
            if (j <= cols - 4) {
                maxProduct = Math.max(maxProduct, grid[i][j] * grid[i][j + 1] * grid[i][j + 2] * grid[i][j + 3]);
            }
            // Vertical
            if (i <= rows - 4) {
                maxProduct = Math.max(maxProduct, grid[i][j] * grid[i + 1][j] * grid[i + 2][j] * grid[i + 3][j]);
            }
            // Diagonal (left to right)
            if (i <= rows - 4 && j <= cols - 4) {
                maxProduct = Math.max(maxProduct, grid[i][j] * grid[i + 1][j + 1] * grid[i + 2][j + 2] * grid[i + 3][j + 3]);
            }
            // Diagonal (right to left)
            if (i >= 3 && j <= cols - 4) {
                maxProduct = Math.max(maxProduct, grid[i][j] * grid[i - 1][j + 1] * grid[i - 2][j + 2] * grid[i - 3][j + 3]);
            }
        }
    }
    return maxProduct;
}

Time, Space, and Big O

  • Time Complexity: O(n^2)
  • Space Complexity: O(1)

Problem 12: Highly Divisible Triangular Number

Understanding

A triangular number is a number that can be represented as a triangle with dots. Your task is to find the first triangular number that has over 500 divisors.

Brute-Force Logic

Generate triangular numbers and count their divisors until you find one with more than 500 divisors.

Python and JavaScript Implementations

Python:

def count_divisors(n):
    count = 0
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            count += 2  # i and n/i
    return count

def compute():
    n = 1
    triangular_number = 0
    while True:
        triangular_number += n
        if count_divisors(triangular_number) > 500:
            return triangular_number
        n += 1

JavaScript:

function countDivisors(n) {
    let count = 0;
    for (let i = 1; i <= Math.sqrt(n); i++) {
        if (n % i === 0) {
            count += 2;  // i and n/i
        }
    }
    return count;
}

function computeTriangularNumber() {
    let n = 1;
    let triangularNumber = 0;
    while (true) {
        triangularNumber += n;
        if (countDivisors(triangularNumber) > 500) {
            return triangularNumber;
        }
        n++;
    }
}

Time, Space, and Big O

  • Time Complexity: O(n \sqrt{n})
  • Space Complexity: O(1)

Problem 13: Large Sum

Understanding

You have a list of 100 50-digit numbers. Your task is to find the first ten digits of the sum of these numbers.

Brute-Force Logic

Sum up all the numbers and take the first ten digits of the sum.

Python and JavaScript Implementations

Python:

def compute(numbers):
    total_sum = sum(numbers)
    return str(total_sum)[:10]

JavaScript:

function computeLargeSum(numbers) {
    const totalSum = BigInt(numbers.reduce((a, b) => BigInt(a) + BigInt(b), 0));
    return totalSum.toString().substring(0, 10);
}

Time, Space, and Big O

  • Time Complexity: O(n)
  • Space Complexity: O(1)

Problem 14: Longest Collatz Sequence

Understanding

The Collatz sequence starts with any positive integer n. The next term in the sequence is n/2n/2 if n is even, and 3n + 13n+1 if n is odd. The sequence ends when it reaches 1. The problem asks you to find the number below one million that produces the longest Collatz sequence.

Brute-Force Logic

Iterate through all numbers below one million and generate their Collatz sequences, keeping track of the longest one.

Python and JavaScript Implementations

Python:

def collatz_length(n):
    length = 1
    while n > 1:
        length += 1
        if n % 2 == 0:
            n //= 2
        else:
            n = 3 * n + 1
    return length

def compute():
    max_length = 0
    number = 0
    for i in range(1, 1000000):
        length = collatz_length(i)
        if length > max_length:
            max_length = length
            number = i
    return number

JavaScript:

function collatzLength(n) {
    let length = 1;
    while (n > 1) {
        length++;
        if (n % 2 === 0) {
            n /= 2;
        } else {
            n = 3 * n + 1;
        }
    }
    return length;
}

function computeLongestCollatz() {
    let maxLength = 0;
    let number = 0;
    for (let i = 1; i < 1000000; i++) {
        const length = collatzLength(i);
        if (length > maxLength) {
            maxLength = length;
            number = i;
        }
    }
    return number;
}

Time, Space, and Big O

  • Time Complexity: O(n log n)
  • Space Complexity: O(1)

Optimized Logic for Problem 14

We can use a technique called memoization to store the length of the Collatz sequence for each starting number. This way, if a sequence hits a starting number for which the sequence length is already known, we can instantly determine the length of the new sequence.

Python and JavaScript Implementations

Python:

memo = {1: 1}

def collatz_length(n):
    if n not in memo:
        memo[n] = 1 + collatz_length(n // 2) if n % 2 == 0 else 1 + collatz_length(3 * n + 1)
    return memo[n]

def compute():
    max_length = 0
    number = 0
    for i in range(1, 1000000):
        length = collatz_length(i)
        if length > max_length:
            max_length = length
            number = i
    return number

JavaScript:

const memo = {1: 1};

function collatzLength(n) {
    if (!memo[n]) {
        memo[n] = 1 + (n % 2 === 0 ? collatzLength(n / 2) : collatzLength(3 * n + 1));
    }
    return memo[n];
}

function computeLongestCollatz() {
    let maxLength = 0;
    let number = 0;
    for (let i = 1; i < 1000000; i++) {
        const length = collatzLength(i);
        if (length > maxLength) {
            maxLength = length;
            number = i;
        }
    }
    return number;
}

Time, Space, and Big O

  • Time Complexity: O(n log n)
  • Space Complexity: O(n)

Problem 15: Lattice Paths

Understanding

You have a 20×20 grid. Starting at the top left corner and only being able to move right and down, how many different paths can you take to reach the bottom right corner?

Brute-Force Logic

Calculate the number of paths recursively for each cell until you reach the destination cell.

Python and JavaScript Implementations

Python:

def count_paths(x, y):
    if x == 0 or y == 0:
        return 1
    return count_paths(x - 1, y) + count_paths(x, y - 1)

# Not recommended to run on a 20x20 grid due to high computation time
# print(count_paths(20, 20))

JavaScript:

function countPaths(x, y) {
    if (x === 0 || y === 0) {
        return 1;
    }
    return countPaths(x - 1, y) + countPaths(x, y - 1);
}

// Not recommended to run on a 20x20 grid due to high computation time
// console.log(countPaths(20, 20));

Time, Space, and Big O

  • Time Complexity: O(2n+m), where n and m are the grid dimensions
  • Space Complexity: O(n×m)

Optimized Logic for Problem 15

For a grid of size m \times m×n, the number of unique paths can be calculated using combinatorial math as {{m+n} \choose {m}}(m+n​).

Python and JavaScript Implementations

Python:

import math

def compute():
    m, n = 20, 20
    return math.comb(m + n, m)

JavaScript:

function computePaths() {
    const m = 20, n = 20;
    let result = 1;
    for (let i = 0; i < Math.min(m, n); i++) {
        result *= (m + n - i);
        result /= (i + 1);
    }
    return result;
}

Time, Space, and Big O

  • Time Complexity: O(1) (Since m and n are constants)
  • Space Complexity: O(1)

https://ahmedradwan.dev

Reach out if you want to join me and write articles with the nerds 🙂


© 2024 · Nerd Level Tech

Categories

Social Media

Stay connected on social media