Quiz 81: Print prime numbers upto N where 1<=N<=1000000

Problem:

Given a positive integer N, print all prime numbers upto N

Input Format: 

positive integer N

Output Format: 

prime numbers from 0 to N in new line

Constraints: 

1<=N<=1000000

Sample Input

20

Sample Output:

2
3
5
7
11
13
17
19

Explanations:

Prime numbers upto 20

---

Solution:

use strict;
use warnings;

chomp(my $n=<>);
if($n>1)
{
print "2\n";
}
my @arr=(2);
for (my $i=3; $i<=$n;$i+=2) {
    my $isprime = 1;
    my $c = sqrt($i) + 1;
    foreach my $p (@arr) {
        if ($p >= $c) {
            last;
        }
        if ($i % $p == 0) {
            $isprime = 0;
            last;
        }
    }
    if ($isprime == 1) {
print "$i\n";
push(@arr, $i);
    }
}

---

Tips:

This algorithms is fastest method to print prime numbers upto 1000000

Quiz 80: Remove leading zeros from an array of positive integers

Problem:

Given an array of positive integers, display an array after removing all the leading zeros from original array.

Input Format: 

array having elements separated by "space"

Output Format: 

array having elements separated by "space" after removing leading zeros

Constraints: 
Each element of array is < 1000000

Sample Input

007 70 01022 0000000001 00200 20000 0012300

Sample Output:

7 70 1022 1 200 20000 12300

Explanations:

Simple, removed all zeros before first non-zero character

---

Solution:

use strict;
use warnings;

chomp(my $line=<>);
my @arr=split(" ",$line);
@arr=map{$_%1000000}@arr;
print "@arr";

---

Tips:

Use mod of maximum value ie 1000000 in our case.

Quiz 79: Print a square matrix in anti-clockwise direction

Problem:

Given a positive integer(n), print square matrix(n x n) in anticlockwise direction.
Check sample input/output for better understanding

Input Format: 

N=a positive integer

Output Format: 

square matrix in anti-clockwise direction

Constraints: 
None

Sample Input

4

Sample Output:

1 12 11 10
2 13 16 9
3 14 15 8
4 5 6 7

Explanations:

in a matrix, 4 x 4, starting printing numbers from 1 in anticlockwise direction ie down,right,up,left.

---

Solution:

use strict;
use warnings;

my $n=<STDIN>;
my $m=$n;
my @arr=();
my $ans=1;
my $row=0;
my $col=$n-1;
my $i=0;
my $j=0;
while($n>=1)
{
for($i=$row;$i<=$col;$i++)
{
$arr[$i][$row]=$ans;
$ans++;
}
for($i=$row+1;$i<=$col;$i++)
{
$arr[$col][$i]=$ans;
$ans++;
}
for($i=$col-1;$i>=$row;$i--)
{
$arr[$i][$col]=$ans;
$ans++;
}
for($i=$col-1;$i>=$row+1;$i--)
{
$arr[$row][$i]=$ans;
$ans++;
}
$n=$n-2;
$row=$row+1;
$col=$col-1;
}
for($i=0;$i<$m;$i++)
{
for($j=0;$j<$m;$j++)
{
print "$arr[$i][$j] ";
}
print "\n";
}

---

Tips:

On completing 1 full anticlockwise cycle, the dimension of matrix will change by 2, so i used $n=$n-2

Quiz 78: Smallest positive integer not in list

Problem:

Given an array of positive numbers. Find the smallest positive integer which is not present in list

Input Format: 

T=number of test cases
Array(integers separated by space in new line for each test case)

Output Format: 

smallest positive integer in each line for each test case

Constraints: 
None

Sample Input

3
1 6 4 2 5 3
1 6 5 4 3 7
2 3 4 5 6 7

Sample Output:

7
2
1

Explanations:

For case 1, smallest positive integer not in list is 7, 1-6 are present, so ans is 7.

---

Solution:

use strict;
use warnings;

chomp(my $t=<>);
for(my $j=0;$j<$t;$j++)
{
chomp(my $line=<>);
my @arr=split(" ",$line);
@arr=sort{$a<=>$b}@arr;
my $i=1;
my $c=0;
foreach(@arr)
{
if($_==$i)
{
if($_+1!=$i+1)
{
my $tmp=$i;
$tmp++;
print "$tmp\n";
$c++;
last;
}
}
else
{
print "$i\n";
$c++;
last;
}
$i++;
}
if($c==0)
{
print "$i\n";
}
}

---

Tips:

Use sort function so that question could be solved in very less iterations

Quiz 77: Shortest path of directed Graph

Problem:

Given distances between different vertices, find the shortest path from vertex i to vertex j

Input Format: 

N ie no of direct path from one vertex to another
Next N lines have format- vertexA vertexB distance
vertexI vertexJ

Output Format: 

shortest path
length of shortest path

Constraints: 
None

Sample Input

11
a b 5
c a 5
a d 10
e c 12
d f 13
f d 1
a e 2
e a 4
f e 2
e f 1
b d 3
a d

Sample Output:

a e f d
4

Explanations:

shortest path from a to d is a-e-f-d

---

Solution:

#!/usr/bin/perl
use warnings;
use strict;

use Graph;
use Graph::Directed;

my $g = 'Graph::Directed'->new;

chomp(my $n=<>);
for(my $i=0;$i<$n;$i++)
{
my $tmp=<>;
my @arr=split(" ",$tmp);
$g->add_weighted_edges(@arr);
}

my $APSP = $g->APSP_Floyd_Warshall;

chomp(my $in=<>);
(my $u,my $v)=split(" ",$in);
        my $w = $APSP->path_length($u, $v);

        if ($w) {
            my @p = $APSP->path_vertices($u, $v);
    foreach(@p)
{
print "$_ ";
}
    print "\n$w";
        }

---

Tips:

Use module Graph for such problems

Quiz 76: Find all continuous substrings of all lengths

Problem:

Given a string, you have to all continuous substrings of different lengths
Ex for abc, print a,ab,abc,b,bc,c

Input Format: 

A String

Output Format: 

Different substrings in each line

Constraints: 
None

Sample Input

perl

Sample Output:

p
pe
per
perl
e
er
erl
r
rl
l

Explanations:

all continuous substrings of length 1 to 4

---

Solution:

use strict;
use warnings;

chomp(my $a=<STDIN>);
for (my $i=0; $i<=length($a);$i++) 
{
for (my $j = $i+1;$j<=length($a);$j++) 
{
        print substr($a, $i, $j - $i) . "\n";
}
}

---

Tips:

Length can give length of string directly

Quiz 75: Change array to have unique elements only

Problem:

Given an array, you have to print another array containing only unique elements ie removing duplicate elements

Input Format: 

Array->Each element separated by space

Output Format: 

Unique Array->Each element separated by space

Constraints: 

None

Sample Input

1 3 4 2 3 5 7 7 7 4 9 0 0 2

Sample Output:

1 3 4 2 5 7 9 0

Explanations:

removed duplicate elements from original array

---

Solution:

use strict;
use warnings;

sub unique {
    my %found;
    grep !$found{$_}++, @_;
}

chomp(my $in=<STDIN>);
my @array = split(" ",$in);
@array = unique(@array);
foreach(@array)
{
print "$_ ";
}

---

Tips:

Learn use of Hash and Grep

Quiz 74: Rearranging elements of list

Problem:

Input is a list containing N numbers from 1 to N in random order.
Rearrange the list in such a way that "position of ith element is the value of ith element of list.
ie for 4 1 2 3:
new position of 4 should be value of 4th element ie 3rd
new position of 1 should be value of 1st element ie 4th
new position of 2 should be value of 2nd element ie 1st.
new position of 3 should be value of 3rd element ie 2nd.
So new arrangement would be 2 3 4 1

Input Format: 

list containing N numbers from 1 to N in random order

Output Format: 

list after rearrangement

Constraints: 

None

Sample Input

5 6 1 8 3 7 2 4

Sample Output:

3 7 5 8 1 2 6 4

Explanations:

Explained in problem statement

---

Solution:

chomp($input=<STDIN>);
@arr=split(" ",$input);
foreach(@arr)
{
$arr1[$arr[$_-1]-1]=$_;
}
foreach(@arr1)
{
print "$_ ";
}

---

Tips:

Remember that in perl , array index starts with 0

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