## 12 February 2015

### 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

20

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

## 3 February 2015

### 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.

## 1 February 2015

### 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

4

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

## 22 January 2015

### 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

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

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

### 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

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

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);
}

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

## 4 January 2015

### 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

None

### Sample Input

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

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