Quiz 25: Find the highest sum with N rotations

Problem:

Given an array of numbers. SUM is denoted as 1 * 1st element + 2 * 2nd element +.....+ N * Nth element.
The array can be rotated in such a manner that 1st element goes to last and 2nd element becomes 1st element and SUM can be calculated again. So, for all N rotations find the highest SUM

Input Format: 

array elements separated by space

Output Format: 
Highest SUM

Constraints: 
none

Sample Input

5 -2 4 1 -4

Sample Output:
21

Explanations:-

original string: 5 -2 4 1 -4=> SUM= 5+(2*-2)+(3*4)+(4*1)+(5*-4)=5-4+12+4-20=-3
1st rotation: -2 4 1 -4 5=>SUM= -2+(2*4)+(3*1)+(4*-4)+(5*5)=-1+8+3-16+25=-1
2nd rotation: 4 1 -4 5 -2=>SUM= 4+(2*1)+(3*-4)+(4*5)+(5*-2)=4+2-12+20-10=4
3rd rotation: 1 -4 5 -2 4=>SUM= 1+(2*-4)+(3*5)+(4*-2)+(5*4)=1-8+15-8+20=20
4th rotation: -4 5 -2 4 1=>SUM= -4+(2*5)+(3*-2)+(4*4)+(5*1)=-4+10-6+16+5=21
so highest SUM is 21

---

Solution:

chomp($t=<STDIN>);
@arr=split(" ",$t);
$len=@arr;
$high=0;
for($i=1;$i<=$len;$i++)
{
$high=$high+($arr[$i-1] * $i);
}
$o=$high;
foreach(@arr)
{
$sum+=$_;
}
for($j=0;$j<$len;$j++)
{
$o=$o-$sum+($len*$arr[0]);
if($o>$high)
{
$high=$o;
}
my $first = shift @arr;
$arr[$len-1]=$first;
}
print "$high";

---

Tips:

After each rotation, SUM changes by previous cycle sum-(sum of all elements)+N*1st element

Quiz 24: Find number of players removed

Problem:

There are 5 houses in school and they are represented as R,G,B,Y,L. A school teacher ask his students to stand in a row. Now, if 2 or more students of same house stand next to each other, the school teacher keeps only 1 of them in row and removes the rest. Find number if students removed.

Input Format: 
N-number of test cases

Followed by N lines denoting the row formation

Output Format: 
Number of students removed for each case in different lines

Constraints: 
none

Sample Input

3
RGBYL
RRRRGGGBBYYLLRRRGG
RGGRGRGRGRGYYLYBBRGBYL

Sample Output:
0
11
3

Explanations:-

Case 3, students marked in RED are removed, 3 of them- RGGRGRGRGRGYYLYBBRGBYL

---

Solution:

@output=();
chomp($T=<STDIN>);
for($i=0;$i<$T;$i++)
{
chomp($N=<STDIN>);
@arr=split("",$N);
$len=@arr;
        $count=0;
for($j=0;$j<$len;$j++)
{
if($arr[$j] eq $arr[$j+1])
{
$count++;
}
}
push(@output,$count);
}
foreach(@output)
{
print "$_\n";
}

---

Tips:

Simple enough, just compare two consecutive items and increase count if matches

Quiz 23: Find all cavities within given blocks

Problem:

We have N x N Blocks. Each block have a depth ranging from 0-9 mts. Now a block is called a "Cavity" if it is not in corner row or column and all other neighboring blocks have less depth. Neighbor is any block which share a common side.
Find all such cavities

Input Format: 
N

Followed by N lines with depth of each block

Output Format: 
Replace all cavities by X

Constraints: 
none

Sample Input

7
4111114
1191111
3111103
1111541
1516132
1111111
6666666

Sample Output:
4111114
11X1111
3111103
1111X41
1X1X132
1111111
6666666

Explanations:-

line 2, 3rd element 9 is greater than all neighbors, so it is a cavity and replaced by X

---

Solution:

chomp($n=<STDIN>);
$str1;
for($i=0;$i<$n;$i++)
{
chomp($s=<STDIN>);
$str1=$str1.$s;
}
@arr=split("",$str1);
$len=@arr;
for($i=$n;$i<$len-$n-1;$i++)
{
if($i%$n==0 or $i%$n==$n-1)
{
next;
}
elsif($arr[$i]>$arr[$i+1] and $arr[$i]>$arr[$i-1] and $arr[$i]>$arr[$i-$n] and $arr[$i]>$arr[$i+$n])
{
if($arr[$i-$n] eq "X" or $arr[$i-1] eq "X")
{
}
else
{
$arr[$i] = X;
}
}
}
for($i=1;$i<$len+1;$i++)
{
print "$arr[$i-1]";
if($i%$n == 0)
{
print "\n";
}
}

---

Tips:

Make a single array and then check if element is cavity

Quiz 22: Find maximum number of kites Prasoon can buy

Problem:

There is a Kite festival organized at Jaipur. Prasoon have Rs N with him and want to buy kites.

He goes to a shop and shopkeeper shows different kites to him. All different kites have unique price and there are only 1 kite of each type.

Now Prasoon want to maximum kites with money with me. Can you find maximum number of kites he can buy.

Input Format: 
N

Prices of different kites available separated by space

Output Format: 
Count of maximum numbers of kites Prasoon can buy

Constraints: 
none

Sample Input

50
1 34 46 3 8 11 200 16 24 2 33 5 

Sample Output:
7

Explanations:-

1+2+3+5+8+11+16<50, so count is 7

---

Solution:

chomp($n=<STDIN>);
chomp($str2=<STDIN>);
@arr2=split(" ",$str2);
@arr2=sort{ $a <=> $b }(@arr2);
$count=0;
$cost=0;
$i=0;
do
{
$cost=$cost+$arr2[$i];
$count++;
$i++;
}while($cost<=$n);
$count--;
print "$count";

---

Tips:

Sort the prices first and them add them till all money is used.

Quiz 21: Find number of deletions required to make 2 strings anagram

Problem:

Two strings are anagram if they have same character set. like abcde and deacb are anagram. Given 2 strings, you can delete characters from both to ensure that they become anagram. Find total number of deletions required.

Input Format: 
String1 containing only lower case alphabets
String2 containing only lower case alphabets

Output Format: 
total count of deletion required

Constraints: 
none

Sample Input

aaabyz
aakkyb

Sample Output:
4

Explanations:-

Common characters are a,a,b,y. So a,z need to be deleted from string 1 and k,k need to be deleted by string 2. So total deletions are 2+2=4

---

Solution:

$count = 0;
@arr3 = qw(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0);
@arr4 = qw(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0);

chomp($comp1=<STDIN>);
chomp($comp2=<STDIN>);

$all = "abcdefghijklmnopqrstuvwxyz";
$a1 = $all.$comp1;
@arr1 = split("",$a1);
@arr1 = sort(@arr1);
$a1 = join("",@arr1);
my $tmp = 0;
for(my $i=0;$i<@arr1;$i++)
  {
  if($arr1[$i] eq $arr1[$i+1])
       {
         $tmp++;
       }
   else{ 
       push(@arr3,$arr[$i].$tmp);
       $tmp = 0;
       }
   } 
for($i=1;$i<=26;$i++)
{
shift(@arr3);
}

$a2 = $all.$comp2;
@arr2 = split("",$a2);
@arr2 = sort(@arr2);
$a2 = join("",@arr2);
my $tmp = 0;
for(my $i=0;$i<@arr2;$i++)
  {
  if($arr2[$i] eq $arr2[$i+1])
       {
         $tmp++;
       }
   else{ 
       push(@arr4,$arr[$i].$tmp);
       $tmp = 0;
       }
   } 
for($i=1;$i<=26;$i++)
{
shift(@arr4);
}

$count=0;
for($j=0;$j<26;$j++)
{
if($arr3[$j]>$arr4[$j])
{
$count = $count + $arr3[$j] - $arr4[$j];
}
elsif($arr3[$j]<$arr4[$j])
{
$count = $count + $arr4[$j] - $arr3[$j];
}
}
print "$count";

---

Tips:

Find occurrence of all alphabets a-z in both strings and then subtract them

Quiz 20: Write a program for Quicksort

Problem:

Explain quicksort sort 

Input Format: 
unsorted array

Output Format: 
sorted array

Constraints: 
none

Sample Input

8 1 4 -2 6 3

Sample Output:
-2 1 3 4 6 8

Explanations:-

Quick Sort will select a pivot and rearrange elements to its right and left. Smaller numbers at left and larger at right. Then apply same logic to left and right elements. List will get sort automatically. 

---

Solution:

sub qsort {
    return if not @_;
    my $pivot = shift @_;
    return (
      qsort( grep { $_ <  $pivot }  @_ ), 
      $pivot,
      qsort( grep { $_ >= $pivot }  @_ ),
    );
}
@arr=(8, 1, 4, -2, 6, 3);
@ab = qsort(@arr);
print "@ab ";

---

Tips:

@_ store the arguments passed to subroutine in form of array

Quiz 19: Explain insertion sort step by step

Problem:

Explain insertion sort step by step ie printing each step line by line

Input Format: 
unsorted array

Output Format: 
sorted array

Constraints: 
none

Sample Input

8 1 4 -2 6 3

Sample Output:
1 8 4 -2 6 3
1 4 8 -2 6 3
-2 1 4 8 6 3
-2 1 4 6 8 3
-2 1 3 4 6 8

Explanations:-

Insertion sort will first sort first 2 elements, then 1st 3, then 1st 4 and so on

---

Solution:

chomp($str=<STDIN>);
@arr =split(" ",$str);
$len=@arr;
for($i=1;$i<$len;$i++)
{
$x = $arr[$i];
$j=$i-1;
while($j>=0 and $x<$arr[$j])
{
$tmp=$arr[$j];
$arr[$j]=$x;
$arr[$j+1]=$tmp;
$j--;
$c++;
}
foreach(@arr)
{
print "$_ ";
}
print "\n";
}

---

Tips:

Insertion sort is efficient for small set of data only. For bigger set, select some other sort algorithm.