CHEFAMPP - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice

Contest

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:

  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;
}
1 Like