22 January 2015

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

11 January 2015

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

7 January 2015

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

4 January 2015

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

1 January 2015

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