If you are new here you can have a look at Part 1

Problem 6: Sum Square Difference

Understanding

Imagine you have a list of numbers from 1 to 100. You’re tasked with finding the difference between the square of the sum of these numbers and the sum of the squares of these numbers. Confused? Don’t be! Basically, you’re doing two things: first, add all the numbers together and square the result; second, square each number individually and then add those squares up. Finally, subtract the second total from the first one.

Brute-Force Logic

Calculate both the square of the sum and the sum of the squares, then find the difference between them.

Python and JavaScript Implementations

Python:

def compute():
    N = 100
    square_of_sum = sum(range(1, N + 1)) ** 2
    sum_of_squares = sum(x ** 2 for x in range(1, N + 1))
    return str(square_of_sum - sum_of_squares)

JavaScript:

function computeSumSquareDifference() {
  const N = 100;
  const squareOfSum = Math.pow((N * (N + 1)) / 2, 2);
  const sumOfSquares = (N * (N + 1) * (2 * N + 1)) / 6;
  return squareOfSum - sumOfSquares;
}

Time, Space, and Big O

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

Problem 7: 10001st Prime

Understanding

In this challenge, you’re on a quest to find the 10,001st prime number. Remember, a prime number is a number greater than 1 that can only be divided by 1 and itself.

Brute-Force Logic

Start from the first prime number, which is 2, and keep checking subsequent numbers to see if they are prime. Keep a count until you reach the 10,001st prime number.

Python and JavaScript Implementations

Python:

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def compute():
    count = 0
    num = 1
    while count < 10001:
        num += 1
        if is_prime(num):
            count += 1
    return str(num)

JavaScript:

function isPrime(n) {
  if (n < 2) return false;
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) return false;
  }
  return true;
}

function compute10001stPrime() {
  let count = 0;
  let num = 1;
  while (count < 10001) {
    num++;
    if (isPrime(num)) {
      count++;
    }
  }
  return num;
}

Time, Space, and Big O

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

Problem 8: Largest Product in a Series

Understanding

You’re given a long string of digits. Your mission is to find the greatest product of 13 adjacent digits within that string.

Brute-Force Logic

Go through the string of digits, taking 13 adjacent digits at a time and calculating their product. Keep track of the largest product you find.

Python and JavaScript Implementations

Python:

def compute():
    digit_str = "73167176531330624919225119674426574742355349194934..."
    largest_product = 0
    for i in range(0, len(digit_str) - 12):
        product = 1
        for j in range(i, i + 13):
            product *= int(digit_str[j])
        largest_product = max(largest_product, product)
    return str(largest_product)

JavaScript:

function computeLargestProduct() {
  const digitStr = "73167176531330624919225119674426574742355349194934...";
  let largestProduct = 0;
  for (let i = 0; i < digitStr.length - 12; i++) {
    let product = 1;
    for (let j = i; j < i + 13; j++) {
      product *= Number(digitStr[j]);
    }
    largestProduct = Math.max(largestProduct, product);
  }
  return largestProduct;
}

Time, Space, and Big O

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

Problem 9: Special Pythagorean Triplet

Understanding

In this problem, you’re looking for three numbers that satisfy two conditions: they must sum up to 1000, and they must form a Pythagorean triplet (i.e., a^2 + b^2 = c^2).

Brute-Force Logic

Loop through possible combinations of aa, bb, and cc to find the triplet that meets both conditions.

Python and JavaScript Implementations

Python:

def compute():
    for a in range(1, 1000):
        for b in range(a, 1000):
            c = 1000 - a - b
            if a * a + b * b == c * c:
                return str(a * b * c)

JavaScript:

function computeSpecialTriplet() {
    for (let a = 1; a < 1000; a++) {
        for (let b = a; b < 1000; b++) {
            const c = 1000 - a - b;
            if (a * a + b * b === c * c) {
                return a * b * c;
            }
        }
    }
}

Time, Space, and Big O

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

Problem 10: Summation of Primes

Understanding

Your task is to find the sum of all prime numbers less than 2 million. A prime number is a number greater than 1 that can only be divided by itself and 1.

Brute-Force Logic

Iterate through numbers less than 2 million and sum up the ones that are prime.

Python and JavaScript Implementations

Python:

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def compute():
    return str(sum(x for x in range(2, 2000000) if is_prime(x)))

JavaScript:

function isPrime(n) {
    if (n < 2) return false;
    for (let i = 2; i <= Math.sqrt(n); i++) {
        if (n % i === 0) return false;
    }
    return true;
}

function computeSumOfPrimes() {
    let sum = 0;
    for (let x = 2; x < 2000000; x++) {
        if (isPrime(x)) {
            sum += x;
        }
    }
    return sum;
}

Time, Space, and Big O

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

Conclusion

In this second part of the article series, we’ve tackled Problems 6 to 10 from Project Euler. We discussed both brute-force and optimized solutions when applicable, and looked at their computational complexities. Whether you prefer Python or JavaScript, these problems offer a great opportunity to improve your coding and problem-solving skills.

Stay tuned for Part 3, where we’ll explore Problems 11 to 15.

Note: The brute-force solutions for some problems are already 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!