Quiz 73: Find the max occurrence of a sum in a series

Problem:

Given an array of N numbers, you have to make all possible sub-arrays having exactly 3 Numbers. Generate sum of each sub-array. Some "Sum" may occur for more than 1 times. Print the Sum which occured maximum number of times and Print the number of times that sum occured. If more than 1 sum occured for max number of times, print the largest sum

Input Format: 

N-length of array
N lines having array elements

Output Format: 

Maximum occurance of any sum is $num times and largest such sum is $sum

Constraints: 

n>3

Sample Input

5
1
4
5
3
6

Sample Output:

Maximum occurance of any sum is 2 times and largest such sum is 12

Explanations:

(1,5,6)=12 and (4,5,3)=12. All rest sum occurs for 1 time only

---

Solution:

chomp($n=<STDIN>);
for($x=0;$x<$n;$x++)
{
chomp($tmp=<STDIN>);
push(@arr,$tmp);
}
%hash;
$max=0;
$num=1;
$check=0;
for($i=0;$i<$n-2;$i++)
{
for($j=$i+1;$j<$n-1;$j++)
{
for($k=$j+1;$k<$n;$k++)
{
#print "$arr[$i] $arr[$j] $arr[$k]\n";
$sum=$arr[$i]+$arr[$j]+$arr[$k];
if($check==0)
{
if($sum>$max){$max=$sum;}
}
if($hash{$sum})
{
$check++;
$hash{$sum}++;
if($num<=$hash{$sum})
{
$num=$hash{$sum};
$max=$sum;
}
}
else
{
$hash{$sum}=1;
}
}
}
}
print "Maximum occurance of any sum is $num times and largest such sum is $max";

---

Tips:

Take care of condition when each sum occur only 1 time

Quiz 72: Flip the bits

Problem:

Given a decimal number, convert it to binary. Flip the bits ie change 0 to 1 and 1 to 0 and then convert back to decimal.

Input Format: 

Decimal Number

Output Format: 

Decimal Number after making changes

Constraints: 

none

Sample Input

5

Sample Output:

2

Explanations:

5 in binary is 101, after flipping bits-010 which in decimal is 2.

---

Solution:

#function to convert binary to decimal
sub con {
    return unpack("N", pack("B32", substr("0" x 32 . shift, -32)));
}


chomp($n=<STDIN>);
$binary = sprintf ("%b",$n);
#print "$binary\n";
@arr=split(//,$binary);
foreach(@arr)
{
if($_ == 0)
{
$_ = 1;
}
else
{
$_ = 0;
}
}
$flip=join("",@arr);
#print "$flip\n";
$ans=con($flip);
print $ans;

---

Tips:

Learn conversion of Decimal to Binary and vice versa.

Quiz 71: Print all combinations of a sentence

Problem:

Given a sentence like "i love perl", print all sentences that can be formed using all words from original sentence.

Input Format: 

A Sentence where words are seprated by single space

Output Format: 

All combinations in different lines

Constraints: 

none

Sample Input

I love perl

Sample Output:

I love perl
I perl love
perl I love
perl love I
love I perl
love perl I

Explanations:

sentence have 3 words , so 6 different combinations

---

Solution:

chomp($line=<STDIN>);
@array=split(" ",$line);

sub fact {
   my $tmp = shift;
   return 1 if $tmp < 2;
   return $tmp*fact($tmp-1);
}

my %seen;
$len=@array;
$count = fact($len);
$nr  = 0;
while( $nr < $count ) {
    $var = 1;
    @arr;
    while( $var ) {
        for( my $i = 0; $i < $len; ++$i ) {
            $arr[$i] = $array[ rand $len ];
        }
        my %unique;
        my $unique = 1;
        for my $c ( @arr ) {
            if( ++$unique{$c} > 1 ) {
                $unique = 0;
            }
        }
        if( $unique == 1 ) {
            $var = 0;
        }
    }

    if( exists $seen{ "@arr" } ) {
        next;
    }
    else {
        local $" = "\t";
        foreach(@arr)
{
print "$_ ";
}
print "\n";
    }
    ++$seen{"@arr"};
    ++$nr;
}

---

Tips:

Use factorial to find number of combinations

Quiz 70: Find the secret code

Problem:

Input is in form of FNAME LNAME AGE, where FNAME and LNAME are uppercase and AGE is numerical.
Secret code is a string which contains first letter of FNAME, first 4 letters of LNAME and reverse of age.
It is guaranteed that LNAME have length atleast 4

Input Format: 

FNAME LNAME AGE

Output Format: 

SECRET NAME

Constraints: 

None

Sample Input

PRIYANKA CHOPRA 31

Sample Output:

PCHOP13

Explanations:

P-CHOP-13

---

Solution:

chomp($str=<STDIN>);
$str=~ /([A-Z])[A-Z]+\s([A-Z]{4})[A-z]+\s(\d+)/;
print $1.$2.reverse($3);

---

Tips:

{4}used to capture 4 characters

Quiz 69: Order of getting Priyanka's autograph

Problem:

N people are standing in a line to take autograph from famous actress "Priyanka". People can be classified to boy, girl, man and woman. Priyanka decided that 1st she will give autograph to 1st girl in the line, then next girl and so on. Then she will follow this rule for woman, then boy and then man.Given input in form of "name classification", print the names in order of getting autograph.

Input Format: 

N
N lines in format "name classification"

Output Format: 

N lines having names

Constraints: 

None

Sample Input

10
saurabh boy
shikha girl
satyam boy
kanchan girl
sameer man
sonali woman
shree man
neelabh boy
sony girl
karishma woman

Sample Output:

shikha

kanchan

sony

sonali

karishma

saurabh

satyam

neelabh

sameer

shree

Explanations:

girls followed by women and so on

---

Solution:

chomp($n=<STDIN>);
for($i=0;$i<$n;$i++)
{
chomp($line=<STDIN>);
($a,$b)=split(" ",$line);
if($b eq 'girl')
{
push(@g,$a);
}
elsif($b eq 'boy')
{
push(@b,$a);
}
elsif($b eq 'man')
{
push(@m,$a);
}
else
{
push(@w,$a);
}
}
foreach(@g){print "$_\n";}
foreach(@w){print "$_\n";}
foreach(@b){print "$_\n";}
foreach(@m){print "$_\n";}

---

Tips:

push names to different classifications

Quiz 68: Convert to uppercase and lowercase

Problem:

Given a Word consisting of both uppercase and lowercase aplhabets. Convert the whole string to either uppercase or lowercase such that number of alphabets which require conversions in minimum ie 'Hello' should be changed to 'hello' and 'HELlo' should be changed to 'HELLO'. If equal possibilty to convert to uppercase or lowercase, then change to lowercase.

Input Format: 

String str

Output Format: 

Uppercase str/Lowercase str

Constraints: 

None

Sample Input

elePHAnTs

Sample Output:

elephants

Explanations:

more lowercase alphabets in original string, so convert to lowercase

---

Solution:

chomp($str=<STDIN>);
while($str=~ /[A-Z]/g)
{
$u++;
}
$l=length($str)-$u;
if($l>=$u)
{
print "\L$str";
}

---

Tips:

use \U or \L to convert string to uppercase/lowercase

Quiz 67: typing namaste

Problem:

Shikhi just learned typing. She still types many unnecessary alphabets.
She wants to type "namaste", but end up typing sting str. Print "YES" if "namaste" can be obtained by deleting  some alphabets from string str, else print "NO". Example, "YES" for "asnamastiie", "NO" for "namteass"

Input Format: 

String str

Output Format: 

YES/NO

Constraints: 

None

Sample Input

aeiounqwsamqwsdaiutstqqwwseqjal

Sample Output:

YES

Explanations:

Red color for namaste- aeiounqwsamqwsdaiutstqqwwseqjal

---

Solution:

chomp($str=<STDIN>);
if($str=~ /n.*a.*m.*a.*s.*t.*e.*/)
{
print "YES";
}
else
{
print "NO";
}

---

Tips:

Simple regex use case

Quiz 66: Find if number is special number

Problem:

Given a number N. N is considered special if for any positive integer i, N=(i*(i+1))/2. Print "YES" if N is special number, else print "NO"

Input Format: 

N

Output Format: 

YES/NO

Constraints: 

None

Sample Input

210

Sample Output:

YES

Explanations:

for i=20,(20*21)/2=210. So 210 is special number

---

Solution:

chomp($n=<STDIN>);
$c=sqrt((8*$n)+1);
if($c == int($c))
{
print "YES";
}
else
{
print "NO";
}

---

Tips:

Solving maths equation, you can narrow down to check if 8N+1 is a perfect square.

Quiz 65: Find index of boy holding the ball

Problem:

There are N boys playing a game. They form a circle and have index from 1 to N clockwise. At the start, boy-1 is holding the ball. He says 1 and gives next person. next person says 2 and gives ball to next to next ie 2nd boy to him and so on. Games ends after N-1 passes. Print N-1 indexes showing index of boy holding the ball

Input Format: 

N

Output Format: 

N-1 indexes showing index of boy holding the ball

Constraints: 

None

Sample Input

11

Sample Output:

2 4 7 11 5 11 7 4 2 1

Explanations:

1+1=2,2+2=4,4+3=7,7+4=11,11+5=16-11=5 and so on

---

Solution:

chomp($n=<STDIN>);
$c=1;
for($i=1;$i<$n;$i++)
{
$c=$c+$i;
$c=$c%$n;
if($c==0){$c=$n;}
print "$c ";
}

---

Tips:

Take care of condition when ball is with last person to reset counter to 1.

Quiz 64: Message from newspaper content

Problem:

Sarita have a newspaper cutting. She wants to make a new message by cutting alphabets from newspaper and paste them on a board. For spaces, she may just leave some space in her board, no need to cut from newspaper. She should take care of Uppercase and Lowercase. Obviously an alphabet taken from newspaper once could not be used again. Given content of newspaper cutting and message, print "YES" or "NO" whether message can be written from newspaper cutting.

Input Format: 

newspaper content
Message content

Output Format: 

YES/NO

Constraints: 

None

Sample Input

my favorite animals are Cat,Lion and Frog

i love to Code and Code

Sample Output:

NO

Explanations:

C appears only 1 times in Newspaper and 2 times in Message.

---

Solution:

chomp($h=<STDIN>);
$h=~ s/ //g;
chomp($s=<STDIN>);
$s=~ s/ //g;
@arr=split(//,$s);
$len=@arr;
foreach($i=0;$i<$len;$i++)
{
if($h =~ /$arr[$i]/)
{
$h=~ s/$arr[$i]//;
}
else
{
print "NO";
exit;
}
}
print "YES";

---

Tips:

Exit the code as soon as 1st not matching condition is met.

Quiz 63: Find the winning team

Problem:

In a cricket tournament, N matches were played. Sunil just have a data about winner of match i. The team with maximum number of wins is the winner of the tournament. Find the winner team. It is guaranteed that there is only 1 winner team.

Input Format: 

N

N lines having a winner if ith match

Output Format: 

name of winner team

Constraints: 

None

Sample Input

10
kkr
kkr
dd
mi
cs
dd
dd
cs
mi
rr

Sample Output:

dd

Explanations:

dd won 3 games which is highest

---

Solution:

chomp($n=<STDIN>);
%hash;
$max=1;
for(1..$n)
{
chomp($tmp=<STDIN>);
if($hash{$tmp})
{
$hash{$tmp}++;
if($hash{$tmp}>$max)
{
$max=$hash{$tmp};
$ans=$tmp;
}
}
else
{
$hash{$tmp}=1;
if($max==1){$ans=$tmp;}
}
}
print $ans;

---

Tips:

Maintain Hash and increment value to find maximum wins

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.

Quiz 61: Find number of matching pairs of brackets

Problem: 

Given a sequence containing only '(' and ')' , find number of matching '()'. Example in ((()())), number of matching pairs are 4. In ()())))(), number of matching pairs are 3.

Input Format: 

Sequence

Output Format: 

Number of Matching pairs

Constraints: 

None

Sample Input

()(()()))))((()()

Sample Output:

6

Explanations:

Pairs marked in different colors are ()(()()))))((()()

---

Solution:

chomp($n=<STDIN>);
@arr=split(//,$n);
$c=0;
$ans=0;
foreach(@arr)
{
if($_ eq '(')
{
$c++;
}
if($_ eq ')' and $c>0)
{
$c--;
$ans++;
}
}
print $ans;

---

Tips:

First find '(' and then matching ')'

Quiz 60: Make the shortest numbers

Problem:

Given a number, find the smallest possible number using the digits of original number without any leading 0

Input Format: 

Number

Output Format: 

Smallest possible number

Constraints: 

None

Sample Input

70205008

Sample Output:

20000578

Explanations:

meets the problem statement

---

Solution:

chomp($a=<STDIN>);
@arr=split(//,$a);
@arr=sort(@arr);
$len=@arr;
$j=0;
for($i=0;$i<$len;$i++)
{
if($arr[$i]==0)
{
$j++;
}
else
{
last;
}
}
if($j>0)
{
$arr[0]=$arr[$j];
$arr[$j]=0;
}
print @arr;

---

Tips:

Sort array and then count number of  leading zeros and code accordingly

Quiz 59: Is the matrix symmetric

Problem:

Given a NxN Matrix(N is odd). Each block contains a letter from A-Z. Find whether matrix is symmetric with respect to central block. Central block for 3x3 matrix is (1,1), index starting from 0.

Input Format: 

N
Next N lines containing content of each row.

Output Format: 

YES/NO- whether matrix is symetric or not

Constraints: 

N is always odd

Sample Input

5
ABFWW
TTTOP
ASDSA
POTTT
WWFBA

Sample Output:

YES

Explanations:

It is symmetric wrt to D(2,2) , example (0,0)=(4,4)=A

---

Solution:

chomp($n=<STDIN>);
$str;
for($i=0;$i<$n;$i++)
{
chomp($tmp=<STDIN>);
$str=$str.$tmp;
}
if($str eq reverse($str))
{
print "YES";
}
else
{
print "NO";
}

---

Tips:

No need to make N arrays and then compare, use string

Quiz 58: Make the sequence increasing

Problem:

Given a sequence, you have to make the sequence increasing by adding a number d any number of times. like if d is 2 and sequence is 5 1, then adding 2 for 3 times will make sequence 5 7 which is in increasing order. Number of moves for this example was 3. Find minimum number of moves required to make the sequence increasing.

Input Format: 

N D(total numbers and number D to be added)

sequence(each number separated by space)

Output Format: 

Minimum number of moves

Constraints: 

None

Sample Input

6 3
1 5 2 22 21 2

Sample Output:

11

Explanations:

new sequence would be 1,5,8(2+3*2),22,24(21+3*1),26(2+3*8), so total=2+1+8=11

---

Solution:

chomp($line1=<STDIN>);
($n,$d)=split(" ",$line1);

chomp($line2=<STDIN>);
@arr=split(" ",$line2);
$ans=0;
for($i=0;$i<$n-1;$i++)
{
if($arr[$i]>=$arr[$i+1])
{
$dif=$arr[$i]-$arr[$i+1];
$num=int($dif/$d)+1;
$ans=$ans+$num;
$arr[$i+1]=$arr[$i+1]+($num*$d);
}
}
print $ans;

---

Tips:

Update array elements and continue comparing