0 - HackerRank IDE

Let's walk through the HackerRank IDE and how it works.

1. Visit Project Euler 1
2. Select the appropriate compiler (top-right corner) => JavaScript (Node.js)

This block of Node.js is what will make HackerRank get inputs and outputs to work with your algorithm. Don't worry too much about this part if you are just starting.

process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
    input_stdin += data;
});

process.stdin.on('end', function () {
    input_stdin_array = input_stdin.split("\n");
    main();    
});

function readLine() {
    return input_stdin_array[input_currentline++];
}

Here comes the fun part, we will work in this function or any other functions we want to add in this second block.

function main() {
    var t = parseInt(readLine());
    for(var a0 = 0; a0 < t; a0++){
        var n = parseInt(readLine());
    }
}

#1 - Multiples of 3 and 5

"If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3,5,6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below N."

There is a multitude of solutions to this problem, let's start with a simple one => Time O(n) & Space O(1). This means, we will go number by number (from 1 to N) and add them up as we go. We will make a loop that goes from 1 to n and store one number at a time.

function main() {
  var t = parseInt(readLine());
  for (var a0 = 0; a0 < t; a0++){
    var n = parseInt(readLine());

    let result = 0

    for (let i = 0; i < n; i++) {

If the number is divisible by 5 or 3, add it to the result

      if (i % 5 === 0 || i % 3 === 0) {
        result += i
      }
    }

and simply print the result after the loop from 1 to N

    console.log(result)
  }
}

Sadly, this solution is not fast enough to pass time requirements. Let's explore the fastest solution in Time O(1). But first we need to understand the formula of the sums of natural numbers.

Solution in Time O(1)

How to calculate the sum from 1 to N?

// Psedo code

if n = 10 then

1 + n   = 11     // 1     +     10
2 + n-1 = 11     //  2    +    9   Same result
3 + n-2 = 11     //   3   +   8    Same result
4 + n-3 = 11     //    4  +  7     Same result
5 + n-4 = 11     //     5 + 6      Same result

11 + 11 + 11 + 11 + 11 = 55
or 
5 x 11 = 55  =>  (10/2) x 11 = 55  => (n/2) x (1 + n) = 55

The sum of all numbers from 1 to 10 is 55

From this pattern we can establish that (n * (n + 1)) / 2 is the formula to calculate the sum of natural numbers from 1 to N.

Now we apply this formula and change it to add only the items divisible by 3

I'll take the sum of natural numbers n/3 and then multiply the answer by 3.

Let's say that a = n/3
our answer would be => a*(a + 1) / 2)*3

If we add the sum of natural numbers n/3 and n/5 and then multiply it by 3 and 5, we will count all numbers divisible by 15 twice. So we need to substract once the sum of the numbers divisible by 15. Let's do this in code.

Check this codepen here

Remember to use BigInt for numbers that exceed 2e53, that's the reason why you will find an 'n' after each number (they become BigInt Numbers). At the end, I return the large BigInt Number as a string without the 'n'. Also remember to never mix regular numbers with BigInt Numbers.

#2 - Even Fibonacci numbers

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: 0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...
By considering the terms in the Fibonacci sequence whose values do not exceed N, find the sum of the even-valued terms.

Note that every 3 numbers (in red) are pair numbers, this pattern will help us solve the problem.

Check this codepen here

#3 - Largest prime factor

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

In this algorithm it is important to know that a number cannot be divided by a greater (prime) number than the square root of the number N. For that reason, the approach I decided to take is to divide N by 2 for as long as N is divisible by 2, and then divide N by 2 at each iteration. Then I make a loop to eliminate each possible divisible number until I reach square root of N. Lastly, I retrieved N with all the transformations it went through.

Check this codepen here

#4 - Largest palindrome product

A palindromic number reads the same both ways. The smallest 6 digit palindrome made from the product of two 3-digit numbers is 101101 = 143 x 707. Find the largest palindrome made from the product of two 3-digit numbers which is less than N.

I created a simple function to help me find palindromes

function testPalindrome(n) {
  return n.split("").reverse().join("");
}

Create a list of palindromes and store it in the variable "numbers" before any input gets passed in.

for (let i = 100; i < 1000; i++) {
  for (let j = i; j < 1000; j++) {
    number = i * j;
    if (number == testPalindrome(String(number))) {
      numbers.push([number, i, j])
    }
  }
}

Check each input and see what is the highest palindrome in the "numbers list" but yet smaller than N (the input).

for(var a0 = 0; a0 < t; a0++){
  var n = parseInt(readLine());
  let maxPal = 0
  for (let i = 0; i < numbers.length; i++) {
    if ( maxPal < numbers[i][0] && numbers[i][0] < n) {
      maxPal = numbers[i][0]
    }
  } 
  console.log(maxPal)
}

Check this codepen here

#5 - Smallest multiple

"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(divisible with no remainder) by all of the numbers from 1 to N?"

function main() {
  var t = parseInt(readLine());
  for (var a0 = 0; a0 < t; a0++){
    var n = BigInt(parseInt(readLine()));
    let result = 1n
    for (let i = 1n; i <= n; i++) {
      result *= i
    }
    
    for (let i = 2n; i <= n; i++) {
      let resTest = result/i
      for (let j = 2n; j <= n; j++) {
        if (resTest % j === 0n) {}
        else { break }
        if (j === n) {
          result /= i
          i--
        }
      }
    }
    console.log(String(result).slice(0, result.length))
  }
}