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

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.

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

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