## 15 November 2014

### Quiz 49: Find the subset with minimum- Max(subset)-Min(subset)

Problem:
Given T number, you have to select N numbers such that Max(Selection)-Min(Selection) is minimum. Print Max(Selection)-Min(Selection)
ex: if T=3 and N=2 and numbers are 1,2,4 , then selection can be (1,2) or(2,4) or (1,4).
max(1,2)-min(1,2)=2-1=1
max(2,4)-min(2,4)=4-2=2
max(1,4)-min(1,4)=4-1=3
Clearly 1 is minimum, so output should be 1.

Input Format:
Total number T
Subset number N
next T lines having numbers

Output Format:
Max(Selection)-Min(Selection)

Constraints:
none

Sample Input
7
3
2
6
10
12
4
11
16

Sample Output:
2

Explanations:
We have to select 3 numbers from 7 numbers- 2,6,10,12,4,11,16.
We should select 10,11,12. Max(10,11,12)=12. Min(10,11,12)=10. Diff=2. All other possible combinations have difference more than 2.

Solution:

chomp(\$t=<STDIN>);
chomp(\$n=<STDIN>);
for(\$i=0;\$i<\$t;\$i++)
{
chomp(\$tmp=<STDIN>);
push(@arr,\$tmp);
}
@arr=sort{\$a<=>\$b}@arr;
\$ans=\$arr[\$t-1];
\$up=\$t-\$n;
for(\$i=0;\$i<=\$up;\$i++)
{
\$t=\$arr[\$i+\$n-1]-\$arr[\$i];
if(\$t<\$ans){\$ans=\$t;}
}
print \$ans;

Tips:
Sort all numbers and then calculate for all possible orders using sorted list