Hey there! Welcome to the first part of a fantastic series “Solve Project Euler Problems” 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 1: Multiples of 3 and 5

Understanding

Imagine you’re counting numbers like 1, 2, 3, and so on, all the way up to 999. Now, among those numbers, some are special—they can be divided by either 3 or 5 without leaving a remainder. For example, numbers like 3, 6, 9 (divisible by 3) and 5, 10, 15 (divisible by 5) are what we’re interested in. Your task is to find the sum of all these special numbers below 1000. So you add them all up like 3 + 5 + 6 + 9 + 10 + \ldots3+5+6+9+10+… until you reach numbers below 1000.

Brute-Force Logic

To find these special numbers, we’ll go through each number from 1 up to 999. If the number can be divided by 3 or 5 without leaving any remainder, we’ll add it to our sum.

Python and JavaScript Implementations

Python:

def compute():
    ans = sum(x for x in range(1000) if (x % 3 == 0 or x % 5 == 0))
    return str(ans)

JavaScript:

function computeBruteForce() {
  let sum = 0;
  for (let i = 0; i < 1000; i++) {
    if (i % 3 === 0 || i % 5 === 0) {
      sum += i;
    }
  }
  return sum;
}

Time, Space, and Big O

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

Optimized Logic

We can also solve this problem using a formula that quickly calculates the sum of numbers that can be divided by 3 or 5. This way, we don’t have to go through each number one by one.

Python and JavaScript Implementations

Python:

def sum_of_multiples(n, limit):
    num_terms = (limit - 1) // n
    last_term = num_terms * n
    return (num_terms * (n + last_term)) // 2

def compute_optimized():
    return sum_of_multiples(3, 1000) + sum_of_multiples(5, 1000) - sum_of_multiples(15, 1000)

JavaScript:

function sumOfMultiples(n, limit) {
  const numTerms = Math.floor((limit - 1) / n);
  const lastTerm = numTerms * n;
  return Math.floor((numTerms * (n + lastTerm)) / 2);
}

function computeOptimized() {
  return sumOfMultiples(3, 1000) + sumOfMultiples(5, 1000) - sumOfMultiples(15, 1000);
}

Time, Space, and Big O

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

Problem 2: Even Fibonacci Numbers

Understanding

The Fibonacci sequence starts with 0 and 1, and each following number is the sum of the two before it. Your task is to sum up all the even numbers in this sequence that are less than 4 million.

Brute-Force Logic

Iterate through the Fibonacci sequence, summing up the even terms as you go along.

Python and JavaScript Implementations

Python:

def compute():
    ans = 0
    x, y = 1, 2
    while x <= 4000000:
        if x % 2 == 0:
            ans += x
        x, y = y, x + y
    return str(ans)

JavaScript:

function computeEvenFibonacci() {
  let sum = 0;
  let x = 1, y = 2;
  while (x <= 4000000) {
    if (x % 2 === 0) {
      sum += x;
    }
    [x, y] = [y, x + y];
  }
  return sum;
}

Time, Space, and Big O

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

Note: The brute-force solution for this problem is already pretty efficient, so I haven’t provided an additional optimized solution. However, if you have an innovative approach that could be more efficient, I’d love to hear about it! Feel free to share your ideas in the comments section below.

Problem 3: Largest Prime Factor

Understanding

Imagine you have a giant number, like 600851475143. Your mission is to find the largest number that can divide it perfectly and is also a prime number (meaning it can only be divided by 1 and itself).

Brute-Force Logic

Go through potential divisors one by one, dividing the giant number until you find its largest prime factor.

Python and JavaScript Implementations

Python:

def compute():
    num = 600851475143
    i = 2
    while i * i <= num:
        if num % i:
            i += 1
        else:
            num //= i
    return str(num)

JavaScript:

function computeLargestPrimeFactor() {
  let num = 600851475143;
  let i = 2;
  while (i * i <= num) {
    if (num % i !== 0) {
      i++;
    } else {
      num = Math.floor(num / i);
    }
  }
  return num;
}

Time, Space, and Big O

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

Note: The brute-force solution for this problem is already pretty efficient, so I haven’t provided an additional optimized solution. However, if you have an innovative approach that could be more efficient, I’d love to hear about it! Feel free to share your ideas in the comments section below.

Problem 4: Largest Palindrome Product

Understanding

Your task is to find the largest number that reads the same forwards and backwards (a palindrome) and is the product of two 3-digit numbers.

Brute-Force Logic

Iterate through all combinations of two 3-digit numbers, checking their product to see if it’s a palindrome.

Python and JavaScript Implementations

Python:

def compute():
    ans = max(x * y
              for x in range(100, 1000)
              for y in range(100, 1000)
              if str(x * y) == str(x * y)[::-1])
    return str(ans)

JavaScript:

function computeLargestPalindrome() {
  let maxPalindrome = 0;
  for (let x = 100; x < 1000; x++) {
    for (let y = 100; y < 1000; y++) {
      const product = x * y;
      if (product.toString() === product.toString().split('').reverse().join('')) {
        maxPalindrome = Math.max(maxPalindrome, product);
      }
    }
  }
  return maxPalindrome;
}

Time, Space, and Big O

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

Note: The brute-force solution for this problem is already pretty efficient, so I haven’t provided an additional optimized solution. However, if you have an innovative approach that could be more efficient, I’d love to hear about it! Feel free to share your ideas in the comments section below.

Problem 5: Smallest Multiple

Understanding

You’re given a list of numbers from 1 to 20. Your job is to find the smallest number that can be evenly divided by all the numbers in that list. In other words, you’re looking for a number that has no remainder when divided by any number from 1 to 20.

Brute-Force Logic

Start from the largest number in the list (20) and keep increasing it by 20, then check if each incremented number is divisible by all numbers from 1 to 20.

Python and JavaScript Implementations

Python:

def compute_bruteforce():
    num = 20
    while True:
        if all(num % i == 0 for i in range(1, 21)):
            return str(num)
        num += 20

JavaScript:

function computeSmallestMultipleBruteForce() {
  let num = 20;
  while (true) {
    if (Array.from({length: 20}, (_, i) => i + 1).every(i => num % i === 0)) {
      return num;
    }
    num += 20;
  }
}

Time, Space, and Big O

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

Optimized Logic

Calculate the Least Common Multiple (LCM) of all numbers from 1 to 20.

Python and JavaScript Implementations

Python:

import math

def compute():
    ans = 1
    for i in range(1, 21):
        ans *= i // math.gcd(i, ans)
    return str(ans)

JavaScript:

function gcd(a, b) {
  return b === 0 ? a : gcd(b, a % b);
}

function computeSmallestMultiple() {
  let ans = 1;
  for (let i = 1; i <= 20; i++) {
    ans *= i / gcd(i, ans);
  }
  return ans;
}

Time, Space, and Big O

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

Conclusion

In this part, we dived deep into the first five problems from Project Euler. We looked at both brute-force and optimized solutions where applicable, and we considered their time and space complexities. Whether you’re a Pythonista or a JavaScript aficionado, you can tackle these problems effectively.

Stay tuned for Part 2, where we’ll explore Problems 6 to 10.