LARGSMALL - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: archit
Editorialist: raysh07

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

An integer X is called good if there exists A_i < X and A_j > X, i.e. both larger and smaller. Find the number of good integers X.

EXPLANATION:

Let mx denote \max_{i = 1}^{N} A_i, i.e. the maximum element of the array A, and then let mn denote \min_{i = 1}^{N} A_i, i.e. the minimum element of the array A.

Then some X is good if and only if mn < X < mx. This is because, we can choose A_i = mn and A_j = mx for the given conditions and check.

Thus, we only need to count the number of integers X such that mn < X < mx. This can be done by simply noticing there are exactly \max(mx - mn - 1, 0) such numbers. Alternatively, you can also just bruteforce count all valid X since 1 \le N, A_i \le 100.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's Code (C++) 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int t; cin >> t;
    while (t--){
        int n; cin >> n;
        vector <int> a(n);
        for (auto &x : a) cin >> x;
        
        int mx = *max_element(a.begin(), a.end());
        int mn = *min_element(a.begin(), a.end());
        cout << max(0, mx - mn - 1) << '\n';
    }
    return 0;
}