PROBLEM LINK:
Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1
Author & Editorialist: Vichitr Gandas
Tester: Aryan Choudhary
DIFFICULTY:
EASY
PREREQUISITES:
Basic Maths
PROBLEM:
You are given N non-negative integers A_1,A_2,\ldots,A_N. You are allowed to perform following operation any number of times:
- Choose any valid index i (1≤i≤N) and a positive integer M>0 and replace A_i with A_i \mod M.
- M does not need to be same between different operations.
Find the minimum number of operations to make all the array elements equal.
EXPLANATION
Upper Bound: Upper bound on answer is N by taking mod with 1 we can make all the numbers 0.
Idea: We will try to make all the numbers equal to minimum because we can’t increase by taking mod. Also we can convert any number X to K only if X> 2 \cdot K . So just check if we can make all the numbers equal to minimum.
Also if we can convert a number X to minimum then we can also convert all the numbers >=X. Hence checking for only second minimum number is enough.
Find the count of numbers cnt which are not equal to minimum. If above suggested condition holds for second minimum number then ans is cnt. Otherwise ans is N.
TIME COMPLEXITY:
O(N) per test case
SOLUTIONS:
Setter & Editorialist's Solution
/*
* @author: vichitr
* @date: 25th July 2021
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fast ios::sync_with_stdio(0); cin.tie(0);
void solve() {
int n; cin >> n;
int A[n];
for (int i = 0; i < n; i++)
cin >> A[i];
sort(A, A + n);
int i = 0;
while (i < n and A[i] == A[0])
i++;
int cnt = i;
while (i < n) {
if (A[i] <= A[0] * 2) {
cout << n << '\n';
return;
}
i++;
}
cout << n - cnt << '\n';
}
signed main() {
fast;
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int t = 1;
cin >> t;
for (int tt = 1; tt <= t; tt++) {
// cout << "Case #" << tt << ": ";
solve();
}
return 0;
}
Tester's Solution
/* in the name of Anton */
/*
Compete against Yourself.
Author - Aryan (@aryanc403)
Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/
#ifdef ARYANC403
#include <header.h>
#else
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
//#pragma GCC optimize ("-ffloat-store")
#include<bits/stdc++.h>
#define dbg(args...) 42;
#endif
using namespace std;
#define fo(i,n) for(i=0;i<(n);++i)
#define repA(i,j,n) for(i=(j);i<=(n);++i)
#define repD(i,j,n) for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"
typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;
const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}
long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
return readString(l,r,' ');
}
void readEOF(){
assert(getchar()==EOF);
}
vi readVectorInt(int n,lli l,lli r){
vi a(n);
for(int i=0;i<n-1;++i)
a[i]=readIntSp(l,r);
a[n-1]=readIntLn(l,r);
return a;
}
const lli INF = 0xFFFFFFFFFFFFFFFL;
lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}
class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{ return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y )); }};
void add( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt==m.end()) m.insert({x,cnt});
else jt->Y+=cnt;
}
void del( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt->Y<=cnt) m.erase(jt);
else jt->Y-=cnt;
}
bool cmp(const ii &a,const ii &b)
{
return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}
const lli mod = 1000000007L;
// const lli maxN = 1000000007L;
lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
lli m;
string s;
vi a;
//priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .
lli gcd(lli x,lli y){
if(x==0||y==0)
return x+y;
return __gcd(x,y);
}
int main(void) {
ios_base::sync_with_stdio(false);cin.tie(NULL);
// freopen("txt.in", "r", stdin);
// freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
T=readIntLn(1,1e4);
lli sumN=0;
while(T--)
{
n=readIntLn(1,1e5);
sumN+=n;
assert(sumN<=1e6);
a=readVectorInt(n,0,2e9);
auto solve=[&](){
lli mn=INF,cnt=0;
for(auto x:a){
if(x>mn)
continue;
if(x!=mn)
cnt=0;
cnt++;
mn=min(mn,x);
}
for(auto x:a){
if(mn<x&&x<=2*mn)
return n;
}
return n-cnt;
};
cout<<solve()<<endl;
} aryanc403();
readEOF();
return 0;
}
If you have other approaches or solutions, let’s discuss in comments.If you have other approaches or solutions, let’s discuss in comments.
