Archive for the Algos Category

Tetrahedral Numbers puzzle

Posted in Algos on November 23, 2008 by vinaychilakamarri

Was attending an interview few days ago an I was presented with a good puzzle. The question goes this way:

A pirate arranges his cannon balls as show in the following way:

1

In the first arrangement, there is only one cannon ball. To support it, he inserts 3 cannon balls under it. And to support those 3, 6 would be placed under them and so on. Now if you count the balls in each case it would follow a series like 1 , 4 , 10 …. Write a logic for generating this.

This is interesting puzzle. As we can see, the cannon balls have some embedded pattern in them:

1

1 + (1+2)

1+ (1+2) + (1+2+3)

and so on.

A little math knowledge would help here. If you are aware of the formula for first N natural numbers, it is

N* (N+1) / 2. This can be extended to this puzzle easily to calculate the series. Here is how it can be applied

1*(1+1)/2

1*(1+1)/2 + 2 * (2+1)/2

1*(1+1)/2 + 2 * (2+1)/2 + 3*(3+1)/2

and so on.

As can be seen, we could apply a Sigma operator to condense this formula a little bit:

∑ n * (n+1)/2

for n = 1 to n

Now that we have a cute little Math counter in our hand, we can code it fast. Here is what I did:

public class TetrahedralNumbers {

public static void main(String[] args){

int cannon = 0;
for(int i = 1; i < 14; i++)
{
cannon += (i * (i+1))/2;
System.out.println(cannon);
}
}

}

If you are unaware of the Math part and want to go solving this, there is a slightly inefficient approach that still solves the puzzle:

public class TetrahedralNumbers {

public static void main(String[] args)
{
for (int i = 1; i < 10; i++)
{
int count = 0;

for(int j = 1; j <= i; j++)
{
for(int k = 1; k <= j; k++)
{
count += k;
}
}
System.out.println(count);
}
}

}