Practice

Contest

Easy

# PREREQUISITES:

Sorting, Greedy technique

# PROBLEM:

Given an array of integers, change at most 3 elements so as to minimize the gap between the maximum and minimum element of the array.

# EXPLANATION:

• Changing at most 3 elements is the same as deleting at most 3 elements because you can set them equal to any of the existing elements in the array. When N = 3, make them all the equal.

• So, you can sort the array, and now consider the following cases:

1. Delete 3 largest elements.

2. Delete the smallest element and 2 largest elements.

3. Delete 2 smallest elements and the largest element.

4. Delete 3 largest elements.

Find the gap between maximum and minimum element in all 4 cases, and take the minimum of those.

Time Complexity: \mathcal{O}(N log N).
Bonus: Try to do it in \mathcal{O}(N).

# SOLUTION

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll min_gap(vector<ll>& arr) {
int n = arr.size();
sort(arr.begin(), arr.end());
if (n == 3) {
return 0;
}

int i = n - 4;
int j = 0;
ll res = arr[n - 1] - arr[0];
int cnt = 0;
while (cnt < 4) {
res = min(res, arr[i] - arr[j]);
++i;
++j;
++cnt;
}
return res;
}

int main () {
int t;
cin >> t;

while (t--) {
int n;
cin >> n;

vector<ll> inp(n);
for (auto &x: inp) {
cin >> x;
}

cout << min_gap(inp) << endl;
}
return 0;
}