PROBLEM LINK: Kill The Middle
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Math
PROBLEM:
Given an array A consisting of N distinct integers with N \geq 3, you repeat the following process till the number of elements in the array is less than 3.
● Take the first three elements and find their median. Remove it from the array.
QUICK EXPLANATION:
For every operation, the median element is the element which is neither maximum nor minimum. So, after applying operation, neither the minimum nor the maximum element is affected.
Generalizing above, we can see that the final array shall contain only the minimum and the maximum element of the initial array, in their respective order.
EXPLANATION:
Let us see how the operation works.
The operation takes three elements and finds the median and deletes it. Since all elements are distinct and we are considering three elements, it is easy to see that the median element is never the minimum or the maximum of the three elements. So, after the operation is applied on the triplet, it is the same as removing all three elements from the array and adding back minimum and maximum of three elements, in their order in initial array are added back.
If we keep repeating the above process, in the end, we shall be left only with the minimum and the maximum element in the array. Since the order of elements never changes, we need to print the minimum and the maximum element in their relative order in the initial array.
IMPLEMENTATION:
This solution can be implemented in two ways.
Just by finding the index of minimum and the maximum element in the array and printing the answer.
Simulating the process by noticing that the order of choosing triplets does not matter and using stack and taking the last three elements and adding back minimum and the maximum of triplet for each operation.
SOLUTIONS:
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t = 1;
cin >> t;
while (t--)
{
ll i, j, k, n, m;
cin >> n;
ll a[n], b[n];
for (i = 0; i < n; i++)
{
cin >> a[i];
b[i] = a[i];
}
sort(b, b + n);
ll x = b[0];
ll y = b[n - 1];
for (i = 0; i < n; i++)
{
if (a[i] == x || a[i] == y)
cout << a[i] << " ";
else
continue;
}
cout << "\n";
}
return 0;
}