ACM 2031. Overturned Numbers

  The task statement gives us a great hint, specifically the picture in the statement, that is the longest possible sequence, since 2 3 4 5 7 are unreadable this means that the last digits of the sequences must be 8,9,0,1 at best case which has a length 4.

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::Algorithms::Bit Manipulation::Flipping bits

    By simply switching all the bits we will jump from our current position to the exactly mirrored positioned. The value will be max(int) - number, where maximum int is 4294967295.

HackerRank::Algorithms::Search::Connected Cell in a Grid

  We just need to implement the process where we get flood the region. Both recursive and non-recursive approach is ok, I did the recursive one because it is somewhat shorter to write. Have a look at it below.

HackerRank::Algorithms::Strings::Bigger is Greater

  There is a good function in "algortihm" library which handles the next permutation formation. Check the usage of that function below. It simply takes two arguments iterator first and the iterator last.

HackerRank::Algorithms::Strings::Two Strings

 This task might look a little hard from the first look, but it will become extremely easy when you realize that only checking the existence of single letters form a to z is enough to answer the question ;)

HackerRank::Algorithms::Strings::Anagram

  Like the previous task about anagrams, there is no difference in which one we will try to turn into another one, the difference of letter quantities is what matters. The rest is implementation based.

HackerRank::Algorithms::Strings::Make it Anagram

  There is no difference whether we try to change the first to look like the second one, of to change the second one to look like the first one. The thing is that if one of them has for example X 'a' letters and the other one has Y 'a' letters, then no matter what we do we need to do abs(X-Y) deletions in order to match the number of 'a' s. We have to do the same for all the 26 letters, in other words the answer is the sum of differences of each letters quantities in the strings.

HackerRank::Algorithms::Strings::Gemstones

  We simply need to check all the letters from a to z to exist in all of the given strings at the same time.

HackerRank::Algorithms::Strings::Game of Thrones - I

   The only thing which we care about is the number of all the letters from a to z. If the string has an even length then we need to have even number of letters of each type so that we can form a palindrome. If the initial string has an odd length, then we need to have exactly one letter repeating odd number of times and the other letters repeating even number of times.


   

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::Algorithms::Strings::Alternating Characters

    We need to have a look at a single deletion, if there are 2 equal adjacent letters then surely one of them has to be deleted and no matter which one we chose to delete, the remaining string is going to be the same, so by simply counting the number of equal adjacent letters and deleting them will give us the final result.

HackerRank::Algorithms::Strings::Pangrams

  we can keep a boolean array MARK where MARK[I] is true if we have already met the Ith letter and false otherwise. Now, we loop over all the letters of the string, lowercase all of them, then check the MARK array, if it's false then we mark that letter as true and increase our counter of unique letters. in the end, if the counter equals to 26 then we have met all the letters, otherwise we didn't.

HackerRank::Algorithms::Strings::Funny String

 One simple loop over the given string is enough to check the task requirement.

HackerRank::Algorithms::Combinatorics::Connecting Towns

    Simple, it's a product of all numbers because simple if there are N ways to move from state 1 to state 2 and M ways to move from state 2 to state 3, then there are total N*M ways to move from state 1 to state 3.

HackerRank::Algorithms::Combinatorics::Minimum Draws

   In the worst case we will pull out first N socks on after another with all different colors, and drawing the N+1 th ensures that at least one of them will match because we have already drawn all the possible different colors.

HackerRank::Algorithms::Combinatorics::Handshake

  The first man shakes hands with 2,3...N, total N-1 handshakes, the second man shakes hands with 3,4..,...N total N-2 handshakes, and so on until the N-1 the one shakes hands with only N th one, we have total handshakes equal to 1+2+3+...+N-1 which equals to  ((N-1)* (N))/2

HackerRank::Algorithms::Graph Theory::Snakes and Ladders: The Quickest Way Up

     BFS is our friend. We keep a queue of pairs where the first element will show us the coordinate of the current node ( the coordinate is a single number) and the number of rolls we made so far. We also should keep a boolean array MARK where  MARK[I] shows whether we have already visited the node I or not. Initially our queue has one element, the coordinate 1 and a distance 0. After that for all the front elements of the queue, we take it out, pop it away, then we look over all the coordinates which are 1,2,3,4,5, or 6 steps away from our current coordinate and if they are not visited then we mark them as visited and push them into the queue. We also need to take care of the snakes and ladders. We can keep an array PATH, where PATH[I] shows us the number of a cell which we would have to travel if we somehow landed on the cell I. Check the source code for a better understanding.

HackerRank::Algorithms::Dynamic Programming::The Maximum Subarray

  Calculating the maximum non-contiguous subarray is pretty obvious, we simply take all the positive numbers and summarize them. Now for the contiguous part,  for calculating it we can use a simple algorithm called "Kadaen Algorithms". I will try to describe it . We keep an integer which shows the best answer we got so far ( we will call it ANS) and one more integer which shows the current sum which we got by summing some elements. Now we begin summing the elements, at every step we update the ANS. and if at some point we got a current sum which is a negative number then there is no need to keep the elements which we summed so far, we would rather drop them and start picking new elements on the way. Check out the source code for a better understanding.

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::Algorithms::Warmup::Sherlock and The Beast

N is maximum 100000, and based on that here is a very very simple solution. Simply take all the numbers which are divisible by 3 which will show the numbers of 5s, then check if the remaining number of digits is divisible on 5, if it is, then we should update our answer, and in the end print it out.

HackerRank::Algorithms::Warmup::Identify Smith Numbers

  We need to prime factorize the number and take the sum of digits of the factors and compare to the sum of digits of the initial number. Factorizing takes somewhat sqrt(N) time so it will fit in the time limit.

HackerRank::Algorithms::Warmup::Kaprekar Numbers

   I chose not to give this much a lot of thinking. I made a little ugly-looking brute-force solution which found the Kaprekar numbers (there are not too many of them, about 20 numbers from 0 to 100000). And then , for getting accepted I just put in those 20 numbers in an array and processed the input.

HackerRank::Algorithms::Warmup::Is Fibo

  80th Fibonacci numbers is much bigger than 10^10 which means even by looping over all the possible numbers for checking whether the given number is a Fibonacci number or not will take something like 10^5 * 80 which is enough for getting AC.

HackerRank::Algorithms::Warmup::Max Min

We simply sort out the array and take the minimum difference of the first and last numbers of every continuous subsequence of length K.

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::Algorithms::Warmup::Filling Jars

  Look at the question carefully " the average number of candies" which means that we don't care about the interval [A,B] all we care for is the total number of candies which can be calculated easily.

HackerRank::Algorithms::Sorting::Insertion Sort - Part 1

  The task clearly states the thing you should do, you need to carefully implement the process of an element finding it's place in a sorted array in a way the task wants you to. I suggest to have a separate function for just printing the array, it will somewhat ease your job.

HackerRank::Algorithms::Sorting::Intro to Tutorial Challenges

  Simply looping over 1000 numbers to find a specific number is an OK idea which will get accepted for sure.

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.

HackerRank::Algorithms::Warmup::Sherlock and Squares

  The first look at the constraints is very important. A,B<=10^9. Among this there are sqrt(1000000000) almost 32000 numbers which are squares of natural numbers. Initially before processing the input, we need to write out all the full square number and store them somewhere. Then after reading the input, we need to loop over all the numbers and check if they are in the given range or not ( be attentive, we need to loop over the number which we found, and check whether they are in the range or not, not vice versa ). 

HackerRank::Algorithms::Warmup::Taum and B'day

  We will call the two types as "cheap" and "expensive", the cheap one obviously is the one which is cheaper than the other. If the prices are equal than there is no difference whether we name the first one as the "cheap" one or the second one. We need to buy all the required gifts off the cheap type. Then, if buying another cheap gift and converting it to the other type is still cheaper than the original price of the expensive gift, then we buy all the first with the "cheap" value and convert the necessary amount to the other type, otherwise we buy the expensive ones with their price.

HackerRank::Algorithms::Warmup::ACM ICPC Team

  The constraints are very low which means that by manually checking all the possible 2 member teams, we will compute the answer. 

HackerRank::Algorithms::Warmup::Manasa and Stones

  There are many ways we can change the numbers and simple checking all the ways will take too long, but we need to notice one thing. No matter how we move we make N-1 moves and every time we change the number either by A or B, which means that the final number is going to be a sum of N-1 numbers which are either A or B. Which means in total there are N-1 possible outcomes where there are X As,  ( 1<=X<=N-1) and N-1-X Bs.

HackerRank::Algorithms::Warmup::Cavity Map

We need to loop over all the cells and check for the 4 neighbors of every cell to be smaller than that cell.

HackerRank::Algorithms::Warmup::Chocolate Feast

  We need to implement the process of buying the chocolates. Initially he buys N/C chocolates. Even if some money is left we don't need to consider it anymore, because we can't by more with money, we need to buy with wrappers. Then we need to buy as many chocolates as we can with the current number of wrappers, then eat the chocolates and see if we have enough wrappers to buy at least one more chocolate, if we do, then do this step again, until we can't buy any more.


        

HackerRank::Algorithms::Warmup::Find Digits

We need to loop over all the digits and check for the divisibility of the number of that digit, there are different ways to do that, one way is to take the reminder of division of 10 and then divide to 10 to get to the next digit.

HackerRank::Algorithms::Warmup::Angry Professor

  We just need to input N number and find the number of numbers which are less or equal than 0. And then compare the result to the given integer K.

HackerRank::Algorithms::Warmup::Lonely Integer

  To keep it short, if we XOR( exclusive OR) all the numbers together, the result will be our answer.
 For not getting too deep into the math proofs, we need to prove 4 properties
1. a^a=0 ( any number XORed with itself is 0)
2. a^0=a (any number XORed with 0 is equal to himself)
3. (a^b)^c=a^(b^c) (the associative rule)
4. a^b=b^a (the commutative rule)
 All those rules are really very obvious to prove.
So, the only thing we need to do is to input all the numbers, XOR them and output the result.

HackerRank::Algorithms::Warmup::The Love-Letter Mystery

  No matter what, we need to change every "pair" to be equal ( by saying pair we understand the letters which need to be equal to one another to form a palindrome like the first and the last, second and the pre-last). Which means if we have a pair of letters A and B and we need to change them in order for them to be equal, we need to do at least absolute (B-A) moves.

HackerRank::Algorithms::Warmup::Maximizing XOR

   The constraints: the interval is at most 10^3 which means that there are at most 10^6 pairs of numbers, so manually checking them and choosing the maximum one is sure going to be accepted.

HackerRank::Algorithms::Warmup::Utopian Tree

   The constraints are very low, so just implementing the cycle of the growth is enough to get accepted.

HackerRank::Algorithms::Warmup::Solve me Second

   The continuation of the A+B task, except this time you need to know loops as well.

HackerRank::Algorithms::Warmup::Solve me First

   The first task of almost any online judge is the A+B task. Not much to tell here.