Hackerrank

HackerRank: Summing the N series

HackerRank: Summing the N series

Finally a problem where we need a little bit of math to solve it. It is called Summing the N series, and when I say a little bit, I mean only a little bit. The problem reads

You are given a sequence whose  term is

 

You have to evaluate the series

 

Find .

Continue reading →

Posted by Kristian in HackerRank, 0 comments
HackerRank: Connecting Towns

HackerRank: Connecting Towns

Welcome to the Shire… Well at least welcome to Middle Earth, we don’t actually need to travel through the shire in the next HackerRank problem with Connecting Towns. The problem reads

Gandalf is travelling from Rohan to Rivendell to meet Frodo but there is no direct route from Rohan (T1) to Rivendell (Tn).

But there are towns T2,T3,T4…Tn-1 such that there are N1 routes from Town T1 to T2, and in general, Ni routes from Ti to Ti+1 for i=1 to n-1 and 0 routes for any other Ti to Tj for j ≠ i+1

Find the total number of routes Gandalf can take to reach Rivendell from Rohan.

Note
Gandalf has to pass all the towns Ti for i=1 to n-1 in numerical order to reach Tn.
For each Ti , Ti+1 there are only Ni distinct routes Gandalf can take.

Input Format
The first line contains an integer T, T test-cases follow.
Each test-case has 2 lines. The first line contains an integer N (the number of towns).
The second line contains N – 1 space separated integers where the ith integer denotes the number of routes, Ni, from the town Ti to Ti+1

Output Format
Total number of routes from T1 to Tn modulo 1234567
http://en.wikipedia.org/wiki/Modular_arithmetic

Solving the math of Connecting Towns

There are two things we need to get our heads around. There is the first part which is how many paths there are, and then there is the second part of the modulo.

The former problem of the paths is rather simple as it is a simple combinatorics problem and the total number of paths are just the product of the paths of each leg of the journey

The problem of the modulo operator can be treated in different ways. Since we are using Python as implementation language we can completely ignore it, as it can handle arbitrarily large integers. However, we can also solve it as we have done for Project Euler problem 48.

In general we have the formula

Which means that for every time we multiply with the next set of paths we can also take the modulo, which means we will keep the total size of the integer down significantly.  If it actually matters in Python I don’t know.

Implementing Connecting towns in Python

Let us implement the one with modulo arithmetic. However since we know that both a and b in the previous formula will be smaller than the modulo. Therefore a%c = a and b%c= b, so we only need to take modulo of the result during the iterations. Therefore the function we need to implement is

def connectingTowns(n, routes):
    paths = 1
    for i in routes:
        paths = (paths * i) % 1234567
    return paths

and that should solve the problem.

Posted by Kristian in HackerRank, 0 comments
HackerRank: Minimum Height Triangle

HackerRank: Minimum Height Triangle

It is always fun to work with triangles in any kind of setting not least problem solving in HackerRank. The problem Minimum Height Triangle is no exception. The problem reads

Given integers b  and a, find the smallest integer h, such that there exists a triangle of height h, base b, having an area of at least a.

image

In case we should have forgotten the primary school mathematics. The area of a triangle is given by

This can be isolated such that we get the height of the triangle instead as

Since we want the minimum integer size we then need to ceil that such that we get

This can be implemented in Python as

def lowestTriangle(base, area):
    return math.ceil(2 * area / base)

I usually write somewhat longer posts. But to be honest, I don’t know what to add to this problem.

Posted by Kristian in HackerRank, 0 comments
HackerRank: Handshake

HackerRank: Handshake

Time to shake hands with a lot of people in the next HackerRank challenge called Handshake. The problem reads

At the annual meeting of Board of Directors of Acme Inc, every one starts shaking hands with everyone else in the room. Given the fact that any two persons shake hand exactly once, Can you tell the total count of handshakes?

Input Format
The first line contains the number of test cases T, T lines follow.
Each line then contains an integer N, the total number of Board of Directors of Acme.

Output Format

Print the number of handshakes for each test-case in a new line.

Continue reading →

Posted by Kristian in HackerRank, 3 comments
HackerRank: Maximum Draws

HackerRank: Maximum Draws

Second round of the fundamental mathematics problems on HackerRank is called Maximum draws.  It asks the following

Jim is off to a party and is searching for a matching pair of socks. His drawer is filled with socks, each pair of a different color. In its worst case scenario, how many socks (x) should Jim remove from his drawer until he finds a matching pair?

Input Format
The first line contains the number of test cases T.
Next T lines contains an integer N which indicates the total pairs of socks present in the drawer.

Output Format
Print the number of Draws (x) Jim makes in the worst case scenario.

Continue reading →

Posted by Kristian in HackerRank, 0 comments
HackerRank: Find the Point

HackerRank: Find the Point

I finally found the math problems on HackerRank which makes me so happy. So let’s getting cracking on the first one called Find the Point. It asks us to

Consider two points,  and . We consider the inversion or point reflection, of point  across point   to be a  rotation of point  around .

Given  sets of points  and , find  for each pair of points and print two space-separated integers denoting the respective values of  and  on a new line.

Continue reading →

Posted by Kristian, 2 comments
HackerRank: Utopian Trees

HackerRank: Utopian Trees

I found another fun little problem at HackerRank called Utopian trees. It is not an easy due to the input constraints. Given how small they are I am pretty sure it could be solved by bruteforce.  The problem description is

The Utopian Tree goes through 2 cycles of growth every year. Each spring, it doubles in height. Each summer, its height increases by 1 meter.

Laura plants a Utopian Tree sapling with a height of 1 meter at the onset of spring. How tall will her tree be after n growth cycles?

Given that the number of test cases is smaller than 10 and the number of cycles are less than 60, it should be pretty obvious that it can be bruteforced. However, there is also a nice analytical solution to this.  Continue reading →

Posted by Kristian in HackerRank, 0 comments
Hackerrank: Forming a magic Square

Hackerrank: Forming a magic Square

I must admit that this problem actually took me a good while to solve. Once you have the right insight on forming a magic Square it is really straight forward. But until that point I was just stuck. Anyway, before rambling on lets get to the actual problem.

We define a magic square to be an  matrix of distinct positive integers from 1 to nwhere the sum of any row, column, or diagonal (of length n) is always equal to the same number (i.e., the magic constant).

Consider a  matrix, s, of integers in the inclusive range [1, 9]. We can convert any digit, a, to any other digit, b, in the range [1, 9] at cost .

Given , convert it into a magic square at minimal cost by changing zero or more of its digits. Then print this cost on a new line.

Note: The resulting magic square must contain distinct integers in the inclusive range [1, 9].

Continue reading →

Posted by Kristian in HackerRank, 0 comments
HackerRank: Between Two Sets in Python

HackerRank: Between Two Sets in Python

I found another really interesting problem on HackerRank called Between Two Sets. It is interesting because there was some math to be applied to the problem. The problem is a part of the implementation series on algorithms. The problem description is

Consider two sets of positive integers,  and . We say that a positive integer, x, is between sets A and B if the following conditions are satisfied:

  1. All elements in A are factors of x.
  2. x is a factor of all elements in B.

In other words, some x is between A and B if that value of x satisfies  for every  in A and also satisfies  for every  in B. For example, if  and  , then our possible x values are 6 and 12.

Given A and B, find and print the number of integers (i.e., possible x‘s) that are between the two sets.

There are some constraints given to the between two sets.  These constraints mean that it will be possible to make a bruteforce solution.  We could test every number between 1 and 100 to see if they satisfy the condition for all numbers in both A and B. However, we can also look at a little bit of math to find some properties of the numbers we are testing. Continue reading →

Posted by Kristian in HackerRank, 1 comment