Quiz 56:Make the text center align

Problem:

You are give N words. Length of each word<=10. You need to make them center aligned keeping max length as 10 ie a 6 letter word should be changed to 10 letter word by adding 2 spaces to right and 2 to left. If length is odd, then keep the word towards left.

Input Format: 

N=number of words
N lines containing a word

Output Format: 

N lines containing center aligned word

Constraints: 

None

Sample Input

10
a
aa
aaa
aaaa
aaaaa
aaaaaa
aaaaaaa
aaaaaaaa
aaaaaaaaa
aaaaaaaaaa

Sample Output:

    a
    aa
   aaa
   aaaa
  aaaaa
  aaaaaa
 aaaaaaa
 aaaaaaaa
aaaaaaaaa
aaaaaaaaaa

Explanations:

O/P is center aligned

---

Solution:

chomp($n=<STDIN>);
for($i=0;$i<$n;$i++)
{
chomp($in=<STDIN>);
@arr=split(//,$in);
$len=@arr;
if($len%2==0)
{
$space_r=(10-$len)/2;
$space_l=$space_r;
}
else
{
$space_r=(10-$len+1)/2;
$space_l=$space_r-1;
}
$ans=(' ' x ($space_l).$in.' ' x ($space_r));
push(@out,$ans);
}
foreach(@out)
{
print "$_\n";
}

---

Tips:

' ' is used to insert space

Quiz 55: Find outgoing traffic of chat server

Problem:

We have a chat application.
Allowed operations are:
1> Adding a person to chat group, format +priyanka
2> Removing a person to chat group, format -sonali
3> Sending a message to chat group, format priyanka:Hi
Now, no traffic is sent to server for adding or removing person. But for every sent message, K bytes(length of message) for each person present in group are sent to server. Like if only Priyanka is there is a group, then Priyanka:Hello will send 5 bytes. If 2 persons are there in group, Priyanka:Hello will send 5x2=10 bytes.
Find total bytes sent to server.
Note: All input data is correct. A person cannot be added if it is already there in group. A person cannot be removed if he/she is not there is group. No two persons have same name.

Input Format: 

Instructions in each line:
+Mohan
+shyam
-shyam
Mohan:Hello how r u

Output Format: 

total bytes sent to server

Constraints: 

None

Sample Input

+priya
+shikha
priya:hey shikha, how r u
shikha:fine, thanks
shikha:lets add sonali
+sonali
shikha:hi sonali
sonali:shikha, personal talks, remove priya
-priya
shikha:tell me now

Sample Output:

249

Explanations:

92(when 2 people in chat) + 135(when 3 people in chat) + 22(when again 2 people). total=249

---

Solution:

$c=0;
$ans=0;
my $input;
while($input=<>) 
{
@arr=split(//,$input);
if($arr[0] eq '+'){$c++;next;}
if($arr[0] eq '-'){$c--;next;}
$len=@arr;
$k=$len;
for($i=0;$i<$k;$i++)
{
$len--;
if($arr[$i] eq ':')
{
$len--;
$ans=$ans+($len*$c);
last;
}
}
}
print $ans;

---

Tips:

No use to maintain HASH for different names since we are just concerned about number of people in chat, not the names of person.

Quiz 54: Change duplicate names by appending with number

Problem:

There is a list of N students with their first names. Now if 2 or more students have same name, you need to change 2nd name to "name1", 3rd name to "name2" and so on. If there is only 1 occurrence of particular name, then it will remain as it is.

Input Format: 

N(number of students)
N lines with 1 name each

Output Format: 
n lines with modified names

Constraints: 
None

Sample Input

10
priya
satyam
shikha
sid
amit
shikha
amit
amit
amit
satyam

Sample Output:
priya
satyam
shikha
sid
amit
shikha1
amit1
amit2
amit3
satyam1

Explanations:
As soon as name "shikha" came for 2nd time, change it to "shikha1" and so on.

---

Solution:

chomp($n=<STDIN>);
%count=();
for($i=0;$i<$n;$i++) 
{
chomp($name=<STDIN>);
if($count{$name}) 
{
$name2=$name . $count{$name};
$count{$name}++;
push(@out,$name2);
} 
else 
{
$count{$name}=1;
push(@out,$name);
}
}
foreach(@out)
{
print "$_\n";
}

---

Tips:

use of PERL hashes

Quiz 53: Find minimum number of moves by King to reach destination

Problem:

In a chess board, only 1 King is left. Given his current position and his destination position, find number of minimum moves, in which king can reach his destinations.
Valid moves are same as that of King in Chess Game.

Input Format: 

T(number of test cases)

Next T lines having initial position and destination position like a1 d7

Output Format: 
T lines having minimum number of moves

Constraints: 
None

Sample Input

5
a1 h8
e4 e4
c2 d5
e7 d2
h2 b1

Sample Output:
7
0
3
5
6

Explanations:
for c2 d5, moves can be c2-d3, d3-d4, d4-d5. So 3 moves minimum

---

Solution:

chomp($t=<STDIN>);
for($i=0;$i<$t;$i++)
{
chomp($line=<STDIN>);
@arr=split(" ",$line);
$arr[0]=~ /(\w)(\d*)/;
$c1=ord($1);
$r1=$2;
$arr[1]=~ /(\w)(\d*)/;
$c2=ord($1);
$r2=$2;
if($c1>$c2)
{
$d1=$c1-$c2;
}
else
{
$d1=$c2-$c1;
}
if($r1>$r2)
{
$d2=$r1-$r2;
}
else
{
$d2=$r2-$r1;
}
if($d1>$d2)
{
push(@out,$d1);
}
else
{
push(@out,$d2);
}
}
foreach(@out)
{
print "$_\n";
}

---

Tips:

Maximum (diff of rows, diff of columns)

Quiz 52: Find winner of card game

Problem:

Few friends are playing cards. There play N rounds. Winner of each round is in format "name points". Points of all other players for that round is 0. Final Winner is the person with maximum total points of all rounds. It is guaranteed that no 2 players will have same maximum total after N rounds. Find the name of person and his/her total score

Input Format: 

N(number of rounds)
N lines in format "name points"

Output Format: 
Name Total_points

Constraints: 
None

Sample Input

10
priya 10
satyam 7
shikha 6
sid 11
amit 7
shikha 6
amit 1
amit 1
amit 2
satyam 4

Sample Output:
shikha 12

Explanations:
Shikha have 6+6=12 points, which are maximum.

---

Solution:

chomp($t=<STDIN>);
for($i=0;$i<$t;$i++)
{
chomp($line=<STDIN>);
push(@arr,$line);
}
foreach(@arr){
($a,$b)=split/ /;
$n{$a}+=$b;
}
$max= (sort {$b<=>$a} values %n)[0];
for(@arr){
($a,$b)=split/ /;
$m{$a}+=$b;
if ($max == $n{$a}) {$ans=$a; last }
}
print "$ans $max";

---

Tips:

use of PERL hashes

Quiz 51: Find titles required to cover the ground

Problem:

Given a rectangular ground of dimension X by Y. And we have square tiles of size A by A. Find minimum number of tiles required to cover the ground.
Note: Tiles cannot be broken, it is OK if titles crosses rectangle boundary.

Input Format: 

X Y A

Output Format: 
Number of tiles

Constraints: 
None

Sample Input

8 10 4

Sample Output:
6

Explanations:
8 x 8 will be covered by 4 titles of 4 x 4. Remaining area 8 x 2 will be covered by another 2 tiles. So total 6 tiles.

---

Solution:

chomp($line=<STDIN>);
($x,$y,$p)=split(" ",$line);
if($x%$p==0)
{
$tmp1=$x/$p;
}
else
{
$tmp1=int($x/$p)+1;
}
if($y%$p==0)
{
$tmp2=$y/$p;
}
else
{
$tmp2=int($y/$p)+1;
}
$ans=$tmp1*$tmp2;
print $ans;

---

Tips:

check x, y for divisibility by a and code accordingly

Quiz 50: Solve the equation

Problem:

Given a equation with operations +,-,* only, You have to find the answer.
Start reading the equation from the right and move towards the left.
So, 1*2+3=>1*5=>5

Input Format: 

Test case number T
Next T lines having an equation

Output Format: 
Solution in each line

Constraints: 
Each operand is single digit number.

Sample Input

3
2+4*8-6
2*2*2-2+8
0+0+0+0+3*2

Sample Output:
-6
32
6

Explanations:
2+4*8-6=2+4*-2=2+-8=-6

---

Solution:

chomp($t=<STDIN>);
for($i=0;$i<$t;$i++)
{
chomp($tmp=<STDIN>);
@arr=split(//,$tmp);
$len=@arr;
if($len == 1)
{
push(@out,$arr[0]);
next;
}
$len--;
for($j=$len;$j>=0;$j--)
{
($a,$b,$c)=($arr[$j],$arr[$j-1],$arr[$j-2]);
if($b eq '+')
{
$ans=$a+$c;
}
elsif($b eq '-')
{
$ans=$a-$c;
}
if($b eq '*')
{
$ans=$a*$c;
}
$arr[$j-2]=$ans;
$j--;
}
push(@out,$a);
}
foreach(@out)
{
print "$_\n";
}

---

Tips:

operate 3 elements of array, get result , then operation it with next 2 elements and so on

Quiz 49: Find the subset with minimum- Max(subset)-Min(subset)

Problem:

Given T number, you have to select N numbers such that Max(Selection)-Min(Selection) is minimum. Print Max(Selection)-Min(Selection)
ex: if T=3 and N=2 and numbers are 1,2,4 , then selection can be (1,2) or(2,4) or (1,4).
max(1,2)-min(1,2)=2-1=1
max(2,4)-min(2,4)=4-2=2
max(1,4)-min(1,4)=4-1=3
Clearly 1 is minimum, so output should be 1.

Input Format: 

Total number T
Subset number N
next T lines having numbers

Output Format: 
Max(Selection)-Min(Selection)

Constraints: 
none

Sample Input

7
3
2
6
10
12
4
11
16

Sample Output:
2

Explanations:
We have to select 3 numbers from 7 numbers- 2,6,10,12,4,11,16.
We should select 10,11,12. Max(10,11,12)=12. Min(10,11,12)=10. Diff=2. All other possible combinations have difference more than 2.

---

Solution:

chomp($t=<STDIN>);
chomp($n=<STDIN>);
for($i=0;$i<$t;$i++)
{
chomp($tmp=<STDIN>);
push(@arr,$tmp);
}
@arr=sort{$a<=>$b}@arr;
$ans=$arr[$t-1];
$up=$t-$n;
for($i=0;$i<=$up;$i++)
{
$t=$arr[$i+$n-1]-$arr[$i];
if($t<$ans){$ans=$t;}
}
print $ans;

---

Tips:

Sort all numbers and then calculate for all possible orders using sorted list

Quiz 48: next different alphabet

Problem:

Given a string, you need to convert to a different string such that consecutive characters should be different. Only operation allowed is to delete any alphabet of string. Find minimum number of deletion required

Input Format: 

number of test cases T
next T lines contains a string to be tested

Output Format: 
Minimum number of deletion required

Constraints: 
none

Sample Input

3
ababa
aaaabbbb
acbbca

Sample Output:
0
6
1

Explanations:
ababa already have proper condition.
aaaabbbb = ab, so 3 a and 3 b deleted, so ans is 3+3=6
acbbca = acbca, so only 1 b need to be deleted

---

Solution:

chomp($t=<STDIN>);
for($i=0;$i<$t;$i++)
{
chomp($s=<STDIN>);
@arr=split("",$s);
$len=@arr;
$len--;
$ans=0;
for($j=0;$j<$len;$j++)
{
if($arr[$j] eq $arr[$j+1])
{
$ans++;
}
}
push(@out,$ans);
}
foreach(@out)
{
print "$_\n";
}

---

Tips:

just increment counter if neighbours are same.

Quiz 47: Find maximum value of XOR

Problem:

Given 2 number, find maximum XOR between them

Input Format: 

num 1
num 2

Output Format: 
Max XOR

Constraints: 
none

Sample Input

5
6

Sample Output:
3

Explanations:
5 XOR 5=0
5 XOR 6=3
6 XOR 6=0, so max is 3.

---

Solution:

chomp($a=<STDIN>);
chomp($b=<STDIN>);
$c=0;
for($i=$a;$i<=$b;$i++)
{
for($j=$i;$j<=$b;$j++)
{
$tmp=$i ^ $j;
if($tmp>$c)
{
$c=$tmp;
}
}
}
print $c;

---

Tips:

Find XOR for all possible combinations and print highest among them

Quiz 46: Find if given number is a Fibonacci number

Problem:

Given a number, determine if it is Fibonacci or not.

Input Format: 

t=number of test cases
followed by t lines having 1 number

Output Format: 
Yes or No for each input

Constraints: 
none

Sample Input

4
8
75025
80000
11111

Sample Output:
Yes
Yes
No
No

Explanations:
series is 0, 1, 1, 2, 3, 5, 8, 13......

---

Solution:

chomp($n=<STDIN>);
for($i=0;$i<$n;$i++)
{
chomp($s=<STDIN>);
$a=(5*$s*$s);
$b=$a+4;
$b=sqrt($b);
$c=int($b);
$d=$a-4;
$d=sqrt($d);
$e=int($d);
if($b == $c or $d == $e)
{
push(@out,'Yes');
}
else
{
push(@out,'No');
}
}
foreach(@out)
{
print "$_\n";
}

---

Tips:

Simple logic- check if 5*num*num+4 or 5*num*num-4 is a perfect sqaure.

Quiz 45: Determine whether number is prime or not

Problem:

Given a number, determine if it is prime or not.

Input Format: 

t=number of test cases
followed by t lines having 1 number

Output Format: 
YES or NO for each input

Constraints: 
none

Sample Input

4
6
1333
45611
5179

Sample Output:
NO
NO
NO 
YES

Explanations:
6 is not prime since can be dived by 2 and 3. 5179 is prime since can be divided by 1 and 5179 only and no other number

---

Solution:

sub prime {
    my $number = shift;
    my $str = 2;
    my $sqrt = sqrt $number;
    while(1) {
        if ($number%$str == 0) {
            return 'NO';
        }
        if ($str < $sqrt) {
            $str++;
        } else {
            return 'YES';
        }
    }
}
chomp($t=<STDIN>);
for($i=0;$i<$t;$i++)
{
chomp($n=<STDIN>);
push(@out,prime($n));

}
foreach(@out)
{
print "$_\n";
}

---

Tips:

Check the function used to determine prime number

Quiz 44: Find the next bigger number with same bits

Problem:

Given a decimal number, find the next bigger decimal number having same numbers of 1's and 0's in binary format as original number. like 11011 and 11110 have same number of 1's and 0's.

Input Format: 

t=number of test cases
followed by t lines having a decimal number

Output Format: 
next big decimal number for each input in new line

Constraints: 
none

Sample Input

2
21
44

Sample Output:
22
49

Explanations:
for case 2, 44 in binary is 101100 have 3 1's and 3 0's, next bigger number with same bits is 110001 ie 49.

---

Solution:

$n=<STDIN>;
while($n>0)
{
$a=<STDIN>;
$b=sprintf("%b",$a);
$b='0'.$b;
$b=~s/(.*)01(.*)/$1 10 $2/;
$q=join '',sort split('',$2);
$b=~s{(.*)$2}{$1$q};
$b=~s/\s//g;
$x=oct("0b".$b);
push(@o,$x);
$n--;
}
foreach(@o)
{
print"$_\n";
}

---

Tips:

Next bigger number is formed by finding first 01 from the right and replacing it by 10 , then arranging remaining characters on right to make it minimum, like 1010 to 0011.