//Think simple yet elegant.
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
const ll maxn=100005;
const ll mod=1e9+7;
int main(){
fast;
ll n,i,j,k;
cin >> n;
vector<ll> a(n);
set<ll> hsh;
for(i=0;i<n;i++){
cin >> a[i];
hsh.insert(a[i]);
}
sort(all(a));
ll mx = a[n-1];
ll mn = a[0];
ll t;
while(hsh.size()>1){
hsh.erase(mx);
hsh.insert(mx-mn);
t = min(mx-mn,mn);
auto it = hsh.end();
--it;
mx = *it;
mn=t;
}
cout<<*hsh.begin();
}
Edit: For this test case:
1 2 10e9
your code will run $$$10^9$$$ loops. The test cases were so weak. In those test cases there was not any test case where $$$max\space element - min\space element > 10^5$$$ (or something more) appeared.I dont think so..as the size of the hashset remains constant for quite a time before reducing by 1. Also it doesnt explain the statement in the editorial.
Ok. Try this test case:
1 2 10000000
. It executes in around $$$2$$$ seconds for your code. May be the test cases were weak. My solution is also like you which will give TLE in some cases.