## 22 September 2014

### Quiz 33: Find the index of first even element from a series

Problem:
For 1st row, element of a series is 1, for 2nd row, elements are 1,1,1. From 3rd row onwards, series increases by 1-1 elements at left and right of previous row such that each element is sum of 3 elements of above row(ie element immediately above and elements to left and right).
ie
1st row-                          1
2nd row-                    1   1   1
3rd row-                1   2   3   2   1
4th row-            1   3  6   7   6    3   1 (and so on)

Find the index of 1st element which is even for Nth row. Index starts with 1.

Input Format:
first line, T, contains number of test cases
T lines containing N

Output Format:
Index of first even element for N

Constraints:
N>2

Sample Input
4
3
4
8
98

Sample Output:
2
3
3
4

Explanations:
for 4, series is 1 3 6 7 6 3 1, so 6 is first even number and index is 3.

Solution:

@out=();
chomp($t=<STDIN>); for($i=0;$i<$t;$i++) { chomp($n=<STDIN>);
if($n%2 == 1) { push(@out,2); next; }$trd=$n*($n-1);
$trd=$trd/2;
if($trd % 2 eq 0) { push(@out,3); next; } push(@out,4); } foreach(@out) { print "$_\n";
}

Tips:
If N is odd, answer is 2 always. 3rd elements is n(n-1)/2, check if this is even->answer is 3. Otherwise answer is 4 always.

### Quiz 32: Find symmetric point

Problem:
Given two points, find the symmetric point (C is symmetric point of A and B, if B is mid point of A and C)

Input Format:
first line, T, contains number of test cases
T lines contains coordinates of 2 points A and B

Output Format:
Each line, containing symmetric point of A and B

Constraints:
none

Sample Input
2
0 0 2 2
1 1 3 3

Sample Output:
4 4
5 5

Explanations:
for first test case, 2,2 is midpoint of 4,4 and 0,0

Solution:

@out=();
chomp($t=<STDIN>); for($i=0;$i<$t;$i++) { chomp($c=<STDIN>);
@arr=split(" ",$c);$a=(2*$arr[2])-$arr[0];
$b=(2*$arr[3])-$arr[1]; push(@out,$a);
push(@out,$b); }$len=@out;
for($j=0;$j<$len;$j++)
{
print "$out[$j] $out[$j+1]\n";
$j++; } Tips: Simple, C= 2B-1 ## 16 September 2014 ### Quiz 31: Find the integer without pair Problem: Given a series of integers such that each integer have a pair, only 1 integer is without pair. Find it Input Format: String of integers separated by space Output Format: Integer without pair Constraints: none Sample Input 1 3 5 7 3 5 2 1 2 Sample Output: 7 Explanations: 7 occurs only once, all other appears 2 ie in pair Solution: chomp($line2=<STDIN>);
@arr=split(" ",$line2); @arr=sort{$a<=>$b}@arr;$len=@arr;
for($i=0;$i<$len;$i++)
{
if($arr[$i] != $arr[$i+1])
{
print "$arr[$i]";
exit;
}
$i++; } Tips: Simple enough, sort the list and compare pairs. ## 14 September 2014 ### Quiz 30: Find number of keys which need to get repaired Problem: Given number of broken keyboard keys and a string. Find how many keys need to be repair to type this string Input Format: Broken keys without any spaces String to be typed Output Format: Number of keys which need to be repaired Constraints: none Sample Input aspzq happiness Sample Output: 3 Explanations: keys a,s and p need to be repaired Solution: chomp($n=<STDIN>);
@br=split("",$n);$len=@br;
$count=0; chomp($str=<STDIN>);
@arr=split("",$str);$len1=@arr;
for($j=0;$j<$len;$j++)
{
if($str =~ /$br[$j]/) {$count++;
}
}
print "$count"; Tips: To type p two times, key which need to repaired is key p, so count will not be doubled. ### Quiz 29: Find number of people with weight above average weight Problem: Given weight of N number of people, find number of people whose weight is above average weight Input Format: N followed by N weights Output Format: Number of people whose weight is above average Constraints: none Sample Input 5 42 50 54 58 46 Sample Output: 2 Explanations: Average is 50 and only 54 & 58 are above average, so answer is 2 Solution: chomp($n=<STDIN>);
@arr=split(" ",$n);$len=$arr[0];$first=shift(@arr);
$sum=0; foreach(@arr) {$sum+=$_; }$av=$sum/$n;
@arr=sort{$a<=>$b}(@arr);
$count=0; for($j=$n-1;$j>=0;$j--) { if($arr[$j]>$av)
{
$count++; } else { last; } } print "$count";

Tips:
Shift is used to take out first element of array

### Quiz 28: Find minimum distance to reach the border of rectangle

Problem:
Given a current position and diagonally opposite coordinates of a  rectangle. Find the minimum distance to reach border of rectangle from current position

Input Format:
String x y x1 y1 x2 y2 where x,y is current position, x1,y1 and x2,y2 are opposite coordinates of a rectangle.

Output Format:
Minimum distance

Constraints:
none

Sample Input
1 3 -4 -4 5 5

Sample Output:
2

Explanations:-
Minimum distance is 1,3 to 1,5 ie 2

Solution:

chomp($n=<STDIN>); @br=split(" ",$n);
$d=$br[0]-$br[2]; if($d<0)
{
$d=$d * -1;
}
$tmp=$br[0]-$br[4]; if($tmp<0)
{
$tmp=$tmp * -1;
}
if($d>$tmp)
{
$d=$tmp;
}
$tmp=$br[1]-$br[3]; if($tmp<0)
{
$tmp=$tmp * -1;
}
if($d>$tmp)
{
$d=$tmp;
}
$tmp=$br[1]-$br[5]; if($tmp<0)
{
$tmp=$tmp * -1;
}
if($d>$tmp)
{
$d=$tmp;
}
print "$d"; Tips: Just find the distance from all coordinates and select minimum ### Quiz 27: Find the next bigger lexicographically string Problem: Given a String, find the next bigger lexicographically string. Input Format: String Output Format: next bigger lexicographically string Constraints: none Sample Input zcfedba Sample Output: zdabcef Explanations:- when compare characters from right to left, c < f, next bigger available character to c is d and rest series is sorted order of remaining characters. Solution: chomp($str=<STDIN>);
@arr=split("",$str);$len=@arr;
$count=1; for($j=$len-1;$j>0;$j--) {$count++;
$c1=ord($arr[$j]);$c2=ord($arr[$j-1]);
if($c1>$c2)
{
@r=splice(@arr,$j-1,$count);
@s=sort(@r);
for($m=0;$m<@s;$m++) {$c3=ord($s[$m]);
$c4=ord($r[0]);
$c5=ord($s[$m+1]); if($c3 == $c4 and$c3!=$c5) {$arr[$j-1] =$s[$m+1]; @s1=splice(@s,$m+1,1);
push(@arr,@s);
last;
}
}
last;
}
}
$ans=join("",@arr); print "$ans";

Tips:
Splice is used to remove some elements of array and store them somewhere else.

### Quiz 26: Minimum time for all rats to hide

Problem:
There are n rats and n holes in a straight line. Each hole can accommodate only 1 rat. A rat may move to its right or left. To move 1 block, he needs 1 minute. Find minimum time required for all rats to occupy a hole from their current position.

Input Format:
Line1: position of rats separated by space
Line2: position of holes separated by space

Output Format:
minimum time required

Constraints:
none

Sample Input
1 2 7
0 8 9

Sample Output:
6

Explanations:-
Rat and hole initial positions: O R R _ _ _ _ R O O
So rat 1 will move 1 position left, rat 2 will move 6 position right and rat 3 will move 2 position right, so minimum time for all rats to occupy holes is 6

Solution:

chomp($mouse=<STDIN>); @arrm=split(" ",$mouse);
chomp($holes=<STDIN>); @arrh=split(" ",$holes);
@arrh1=sort{$a<=>$b}@arrh;
@min=();
@h=();
@arrm1=sort{$a<=>$b}@arrm;
$c=0; for($m=0;$m<$n;$m++) { if($arrm1[$m] ==$arrh1[$m]) {$c++;
}
}
$diff=0;$n1=$n; @arrm=sort{$a<=>$b}@arrm;$k=0;
foreach(@arrm1)
{
if($c ==$n)
{
push(@min,$diff); }$diff1 = $_ -$arrh1[$k];$k++;
if($diff1<0) {$diff1 = $diff1 * -1; } push(@min,$diff1);
}
@ans=sort{$a<=>$b}@min;
print "$ans[$n-1]";

Tips:
Sort holes and rat positions and max(h(i)-r(i)) is the answer

## 13 September 2014

### 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 ## 12 September 2014 ### 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 ## 7 September 2014 ### 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