# Max Min

See the original problem on HackerRank.

## Solutions

The problem reduces to choosing 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 #include #include #include #include #include using namespace std; int main() { int N, K; cin >> N >> K; vector v(N); copy_n(istream_iterator(cin), N, begin(v)); sort(begin(v), end(v)); auto tail = 0; auto head = K-1; auto unfairness = INT_MAX; while (head

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

This haskell solution creates N-K+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 K-1 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) 
We've worked on this challenge in these gyms: modena  padua  turin  milan