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!
Table of Contents
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)
Ahmed Radwan
https://ahmedradwan.devReach out if you want to join me and write articles with the nerds 🙂