2 December 2014

Quiz 62: Find the height of tallest tower

Problem:

Cheeku have N wooden blocks of height 1cm and different widths. She can place 2 or wooden blocks over each other a form a tower if width of blocks are same. Find the height of height tower which can be made and number of total tower formed using all the wooden blocks.

Input Format: 

N
width of blocks separated by spaces


Output Format: 

height of highest tower(space)Total number of towers


Constraints: 

None

Sample Input

10
8 1 2 3 1 1 2 2 3 5

Sample Output:

3 5

Explanations:

Tower width,Height= (8,1)(1,3)(2,3)(3,2)(5,1), so max height is 3 and number of towers are 5.



Solution:

chomp($n=<STDIN>);
chomp($line=<STDIN>);
@arr=split(" ",$line);
%hash=();
$max=1;
$ans=$n;
foreach(@arr)
{
if($hash{$_})
{
$hash{$_}++;
$ans--;
if($hash{$_}>$max){$max=$hash{$_};}
}
else
{
$hash{$_}=1;
}
}
print "$max $ans";




Tips:

Maintain Hash and increment value to find max height.

No comments:

Post a Comment