See the original problem on HackerRank.
Solutions
The problem reduces to chosing K consecutive numbers in a sorted list for which the value of D is minimum. Which can be easily done by sorting the given number and calculating D for each group of K consecutive number.
Here is a possible C++ Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iterator>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
int main()
{
int N, K; cin >> N >> K;
vector<int> v(N);
copy_n(istream_iterator<int>(cin), N, begin(v));
sort(begin(v), end(v));
auto tail = 0; auto head = K1;
auto unfairness = INT_MAX;
while (head<N)
{
unfairness = min(unfairness, v[head]v[tail]);
tail++;
head++;
}
cout << unfairness;
}

This results in a combination of zip  map  reduce patterns that in C++ can be written in terms of inner_product
:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <iterator>
#include <vector>
#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;
int main()
{
int N, K; cin >> N >> K;
vector<int> v; v.reserve(N);
copy_n(istream_iterator<int>(cin), N, back_inserter(v));
sort(begin(v), end(v));
K=1;
cout << inner_product(
v.begin()+K, v.end(),
v.begin(), numeric_limits<int>::max(),
[](auto... a) { return min(a...); },
std::minus<int>() );
}

This haskell solution creates NK+1
sublists of length K
, and calculate the minimum and
the maximum of each sublist. The complexity is K * (N  K + 1)
and some tests
fail due to timeout.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

import Data.List (sort)
sublists k xs =
take k xs :
if length xs > k
then sublists k (tail xs)
else []
unfairness ys = maximum ys  minimum ys
minUnfairness k xs = minimum $ unfairness <$> sublists k xs
main = do
_:k:xs < fmap read . lines <$> getContents
print $ minUnfairness k (sort xs)

This haskell solution take advantage of the sorted list. We don’t need to keep
all the items in the sublists, but only extremities, of which one element is the
minimum and the other is the maximum.
To do this, we zip the sorted list, with a copy where the first K1
elements
are missing.
Example with k=3
1
2
3
4
5

 10 20 30 100 200 300 1000
10 20 30 100 200 300 1000 
20 80 170 200 800
^^ 
zipWith ()
generates a new list with the difference of the two
lists. When we have such list, we just need to find the minimum.
1
2
3
4
5
6
7

import Data.List (sort)
minUnfairness k xs = minimum $ zipWith () (drop (k  1) xs) xs
main = do
_:k:xs < fmap read . lines <$> getContents
print $ minUnfairness k (sort xs)
