PROBLEM LINK:
DIFFICULTY:
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:
-
Delete 3 largest elements.
-
Delete the smallest element and 2 largest elements.
-
Delete 2 smallest elements and the largest element.
-
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;
}