HackerRank::Contests::Project Euler::Project Euler #30: Digit Nth powers

   Simple brute force up to 1000000 is enough, although a little optimization would be nice. We can keep an 2D array POW where POW[I][J] shows the I^J. This will help us to calculate the I^J in O(1).

HackerRank::Contests::Project Euler::Project Euler #25: N-digit Fibonacci numbe

  For solving this task I used my little BigInt class again, you can have a look at it below.

HackerRank::Contests::Project Euler::Project Euler #23: Non-abundant sums

precomputations.

   There is a formula for a sum of divisors of a number. if the prime factorization of a number is p1^a1*p2^a2*...*pn^an then the sum of all divisors of the number will be (1+p1+p1^2+...+p1^a1)*(1+p2+p2^2+...+p2^a2)*...*(1+pn+pn^2+..+pn^an)
  We need to calculate all the abundant number before processing the input. Factorization takes sqrt time , but before that we better find primes which will fasten up the process of factorization. We find the primes with the sieve of Eratsotenes (for more info about the sieve visit the "Algorithms" ) section of this blog.
    

HackerRank::Contests::Project Euler::Project Euler #22: Names scores

  C++ map can help us a lot here. Simply calculate all the scores of the names ( by sorting them first) then keep a map which will have a key type string and a value type int. Then simple input the query strings and output the corresponding number form the map.

HackerRank::Contests::Project Euler::Project Euler #18: Maximum path sum I

   This is a little dynamic task. So, we have an input Array A and the answer array ANS where ANS[I][J] shows us the best result of all the paths which end on the cell (I ; J) Initially all the elements of ANS equal to 0 except for the first cell which equals to A[1][1]. Now we loop over ANS for every cell ( I, J ) we can move either to the cell (I+1, J) or (I+1, J+1) and simply
ANS[i+1][j]=max(ANS[i+1][j],ANS[i][j]+A[i+1][j]);
ANS[i+1][j+1]=max(ANS[i+1][j+1],ANS[i][j]+A[i+1][j+1]);
 this basically means that we either leave the cell the way it was, or if the new path is better then we take the new path.

HackerRank::Contests::Project Euler::Project Euler #13: Large sum

  For this task I used my little BigInt class again, you can have a look at it below. It has all the necessary operators except for the division part :(. But still it is enough for this particular task.

HackerRank::Contests::Project Euler::Project Euler #12: Highly divisible triangular number

  Again, pre computing the answers is a good idea, we simply keep an array ANS where ANS[i] shows the answer for I. Now how do we construct ANS? There is a good formula for a number of divisors of a number. If the prime factorization of a number is p1^a1*p2^a2*...*pn^an then the number of divisors is (a1+1)*(a2+1)*...*(an+1). Factorizing the number to prime factors takes sqrt(N) ish time. And also it's a very good idea to store the prime numbers before trying to factorize the number, it will give us some speed boost, and we will do that with the sieve of Eratostenes, if you need more info about the sieve you can find it in this blog in the "Algoruthms" Section.'

HackerRank::Contests::Project Euler::Project Euler #16: Power digit sum

  I didn't think too much on this one, I just used a simple bigInt class written by me. Have a look, it's not too much but it's a simple class of bigInteger which has addition subtraction and multiplication, but no division.

HackerRank::Contests::ProjectEuler::Project Euler #11: Largest product in a grid

   Simple brute force is enough, although we might want to keep everything as short as possible. First of all for avoiding extra border check-ups I suggest to create a layer of depth 3, in other words keep an array of size 26x26 where the actual numbers will be from 4x4 to 23x23 and the rest will be just pure 0s. Next, we need to loop over all the numbers and check 8 type of adjacent numbers (left, right, up ,down, left-up, left-down, right-up, right-down), but clearly we can only do the half of the checks (right, down, right-down, right-up).

HackerRank::Contests::ProjectEuler::Project Euler #10: Summation of primes

 First of all we need to find all the prime numbers up to 1000000. After we found and stored all the prime numbers we need to keep an answer array  SUM where SUM[i] will show the sum of all the prime numbers with index 1 to i. After this we read the number N , find the prime number which doesn't exceed N and output value SUM[index] where index is the index of the greatest prime not bigger than N.

HackerRank::Contests::ProjectEuler::Project Euler #9: Special Pythagorean triplet

   We need to calculate all the answers for all Ns before processing the input. First of all we need to find all the Pythagorean triplets where the sum of that triplet is less than 3000. At worst case, we need to look all the numbers up to 3000. if we have a^2+b^2=c^2, we need to take all the possible pairs a,b and check if the sum of their squares is a full square. Meanwhile, we need to keep an answer array ( we will call it ANS), where ANS[I] shows the answer for the number I. When taking all the triplets, we check for one thing if a+b+c<= 3000, if it is then we need to update the ANS[a+b+c] value. After doing all these, we just need to input the number N and output ANS[N].

HackerRank::Contests::ProjectEuler::Project Euler #8: Largest product in a series

 We simply need to find the maximum of numbers which are formed by multiplying the digit of interval [I;I+K] where I is from [0, N-K]. Maximum of K can be 7, and there are at most 100 test cases each with a maximum length of 10000 which means that a simple brute force is enough to get that green accepted message.

HackerRank::Contests::ProjectEuler::Project Euler #7: 10001st prime

  The 10001st prime number is not a big one, so jsut using a sieve of Eratosthenes for to find the prime numbers up to 5000000 is more than enough. For reading more info about the sieve of Eratosthenes go here.


  

HackerRank::Contests::ProjectEuler::Project Euler #6: Sum square difference

      Pre-calculation can still help. We can calculate the square of the sums in one go, it will be (N*(N+1)/2)^2. And we can build an array named SUM where SUM[i] will be the sum of squares of all numbers from 1 to i. When we are done building this, processing the input takes only a few lines.

 

HackerRank::Contests::ProjectEuler::Project Euler #5: Smallest multiple

    Basically we need to find the highest common multiple of numbers from 1 to N. The method which I suggest might not be the best one, but it's a trustworthy method. I suggest counting it the way we usually count the highest common multiple, which means we find all the prime factors of all the numbers form 2 to N, then for every prime number from 2 to N we pick the maximum power of that prime number which we find in all the number from 2 to N and multiply with out answer. This way we will find the highest common multiple.

HackerRank::Contests::ProjectEuler::Project Euler #4: Largest palindrome product

   Precalculating all the numbers before processing the input , is a very good idea. There are 900x900 possible multiplications, Checking if the number is a palindrome or not is not a hard job, there are various methods for that, you can see my method in the source code below. So, while multiplying we need to take care of the repeating numbers, for that you can simple keep a boolean array B of a length of 1 million, where each B[i] will show whether the number i has been already seen or not. Every time , when you calculate the current multiplication (suppose that number is M), check for B[M], it it's true than just continue to the next pair , otherwise mark it as true and process it. Store all the found palindromes in an array and sort them. After that, processing the input is simply a piece of cake when you have all the numbers calculated and stored in an increasing order.

HackerRank::Contests::ProjectEuler::Project Euler #3: Largest prime factor

  First of all, if the number N doesn't have any divisors from 2 to sqrt(N) that means that N is a prime number. First of all let us calculate all the prime numbers from 1 to sqrt ( maxN) which is sqrt(10^12)=10^6. We will use the sieve of Eratostenes for a faster calculation. After that we need to do the following, loop over all the prime numbers, and check for the divisibility of the number on that prime number , if it is divisible then we divide it as long as it's still divisible , Also we memorize the last prime which divided the number, because we need to find the largest prime factor. After this, we have 2 numbers , the number itself ( or the number which is left from the the division of the initial number on the primes), and the largest prime number which divided the initial number. Now, if the remaining number is a prime number we take the one which is greater from the last 2 mentioned numbers, otherwise we print out the found prime number and exit.

HackerRank::Contests::ProjectEuler::Project Euler #2: Even Fibonacci numbers

  Did you know that the 100th Fibonacci number equals 354224848179261915075 , which is longer than 16 digits,
  Now that you know that, even in the worst case when the number of testcases equals to 10^5 , looping over 100 numbers 10^5 time still won't cause you the Time Limit Exceeded error.

HackerRank::Contests::ProjectEuler::Project Euler #1: Multiples of 3 and 5

   A few things to notice here after which the task will become very easy to solve. Here is a quick question , how many numbers are there from 1 to N that are divisible by 3 ? Simple right? It's N/3 (divide and throw away the remainder). In that case, how to calculate their sum?
3+6+9+...3*M = 3( 1+2+3+...+M). which is equal to (3 * M * (M+1)) /2 (M is the number of numbers in the sequence). The same goes for 5.
   Now we have calculated the sum of all number that are divisible by 3, and we have calculated the sum of all number that are divisible by 5. There are some numbers which are divisible by 15 (both 3 and 5) and we counted them twice , the first time we counted them as a multiple of 3 and the second time we counted it as a multiple of 5. That's why we need to subtract the sum of all number from 1 to N that are divisible by 15 in order to get the final answer.