Min Max

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 = K-1;
    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 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 
comments powered by Disqus