Max Min - Hacker Rank Solution

You will be given a list of integers, , and a single integer . You must create an array of length  from elements of  such that its unfairness is minimized. Call that array .

Unfairness of an array is calculated as

Where:
- max denotes the largest integer in 
- min denotes the smallest integer in 

As an example, consider the array  with a  of . Pick any two elements, test .

Testing for all pairs, the solution  provides the minimum unfairness.

Note: Integers in  may not be unique.

Function Description

Complete the maxMin function in the editor below. It must return an integer that denotes the minimum possible value of unfairness.

maxMin has the following parameter(s):

• k: an integer, the number of elements in the array to create
• arr: an array of integers .

Input Format

The first line contains an integer , the number of elements in array .
The second line contains an integer .
Each of the next  lines contains an integer  where .

Constraints

Output Format

An integer that denotes the minimum possible value of unfairness.

Sample Input 0

7
3
10
100
300
200
1000
20
30

Sample Output 0

20

Explanation 0

Here ; selecting the  integers , unfairness equals

max(10,20,30) - min(10,20,30) = 30 - 10 = 20

Sample Input 1

10
4
1
2
3
4
10
20
30
40
100
200

Sample Output 1

3

Explanation 1

Here ; selecting the  integers , unfairness equals

max(1,2,3,4) - min(1,2,3,4) = 4 - 1 = 3

Sample Input 2

5
2
1
2
1
2
1

Sample Output 2

0

Explanation 2

Here .  or  give the minimum unfairness of .

Max Min - Hacker Rank Solution

In this problem, we are given a list of  numbers, out of which  numbers are to be chosen such that the difference between max and min of  numbers is minimized.

Where anger co-efficient, D = max of chosen K numbers - min of chosen K numbers.

First, we claim that k such numbers can only be obtained if we sort the list and chose k continues numbers. This can easily be proved. Suppose we choose numbers X1, X2, X3,....Xr, Xr+1,....,XK (all are in increasing order but not continuous in the sorted list) i.e. there exists a number p which lies between Xr and Xr+1. So, if we include this number and exclude X1, the new value of D will become |XK-X2| whereas the old value was |XK-X1|. As we know X1<=X2<=XK, the value of D decreases or remains same. Hence, if the chosen K points are not consecutive in the sorted list then we can apply these insertions one or more times to reduce the value of K.

So, 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 in O(NlogN) and calculating D for each group of K consecutive number in O(N-K) time.

Problem Setter's code:

C++

#include <bits/stdc++.h>
    
using namespace std;
    
int main() 
{
    long long int i,n,k,min=999999999,temp;
    cin >> n >> k;
    long long int a[n];
for(i=0;i<n;i++)
cin >> a[i];
sort(a,a+n);
for(i=0;i<=n-k;i++)
{
temp = a[i+k-1]-a[i];
if(temp < min)
min = temp;
}
cout << min << endl;
    
return 0;
}

Problem Tester's code:

Python 2

#!/usr/bin/python
    
N = input()
K = input()
    
assert 1 <= N <= 10**5
assert 1 <= K <= N
    
lis = []
for i in range(N):
    lis.append(input())
    
lis.sort()
    
for i in lis:
    assert 0 <= i <= 10**9
    
answer = 100000000000000000000
    
for index in range(N-K+1):
    diff = lis[index+K-1] - lis[index]
    
    if diff < answer:
        answer = diff
    
print answer