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

2 comments:

  1. #!/usr/bin/perl

    # http://perlquiz.blogspot.in/

    use warnings;
    use strict;

    for (1 .. scalar <>)
    {
    my @list = split ' ', <>; # list of numbers
    my @integers = 0 .. @list+1; # candidate integers
    @integers[@list] = (); # remove list from integers
    print +(grep $_, @integers)[0], "\n"; # print first integer left
    }

    ReplyDelete
  2. Hi
    Your solution gives out of memory error for this simple case:
    1
    777777777

    ReplyDelete