PROBLEM LINKS :
Contest : Division 1
Contest : Division 2
Setter : Tanay Mishra
Tester : Alipasha Montaseri / Kasra Mazaheri
Editorialist : Anand Jaisingh
DIFFICULTY :
Cakewalk
PREREQUISITES :
Programming language basics
PROBLEM :
Given an array A of size N \ge 2 , you need to find if it is possible to delete an element from the array without affecting the original mean of the array.
QUICK EXPLANATION :
It can be proved that we just need to check if the mean of the originally given array exists in the array. If yes, we need to find the lowest index having such an element.
EXPLANATION :
Let’s loop over each element of the array, and check if it is possible to delete this element, such that the mean of the array before and after deleting this element is the same.
Let the sum of the originally given array be sum. So, the mean of the initially given array is the number \frac{sum}{N}. ( this may not necessarily be an integer ). Now, on deleting the element present at index i, the mean transforms to \frac{sum-A[i]}{N-1}
In an ideal world, just checking if these numbers are equal for each i using long doubles would be enough. However, the world is hardly ideal, and to prevent precision issues of any kind, we need :
\frac{sum}{N}=\frac{sum-A[i]}{N-1}. This condition equals :
sum \cdot (N-1) =N \cdot (sum-A[i]) .
Since each of the individual terms we use above are integers, their products are also integers. So, using this condition, we avoid precision issues of all kinds and deal only with integers. We just need to find the lowest i for which this condition holds.
Additionally :
On simplifying the expression above, we get :
N \cdot sum - sum = N \cdot sum - N \cdot A[i] ,
-sum = - N \cdot A[i] ,
\frac{sum}{N} = A[i] .
This condition shows that the element we needed to remove must actually be the mean of the original array. So, we must just find the smallest element i, such that A[i]=\frac{sum}{N}, or print -1 if such an element does not exist.
COMPLEXITY ANALYSIS :
Time Complexity : O(N)
Space complexity : O(N)
SOLUTION LINKS :
Setter
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(void)
{
int t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
ll arr[n];
ll sum=0;
map <ll , int > m;
for(int i=0;i<n;i++)
{
cin>>arr[i];
sum+=arr[i];
if(m[arr[i]]==0)
{
m[arr[i]]=i+1;
}
}
if(sum%n==0)
{
ll mean=sum/n;
if(m[mean]!=0)
{
cout<<m[mean];
}
else{
cout<<"Impossible";
}
}
else{
cout<<"Impossible";
}
cout<<'\n';
}
}
Tester
// KALAM
include<bits/stdc++.h>
using namespace std;
const int N = 100000 + 77;
int n , T;
int a[N];
inline void Test() {
unsigned long long tot = 0;
scanf("%d" , & n);
for(int i = 1;i <= n;++ i)
scanf("%d" , a + i) , tot += a[i];
for(int i = 1;i <= n;++ i)
if(tot * (n - 1) == (tot - a[i]) * n) {
printf("%d\n" , i);
return ;
}
printf("Impossible\n");
}
int main() {
scanf("%d" , & T);
while(T --)
Test();
return 0;
}
Editorialist
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
// Anand Jaisingh
#include<bits/stdc++.h>
using namespace std;
typedef complex<double> base;
typedef long double ld;
typedef long long ll;
#define pb push_back
#define pii pair<int,int>
#define pll pair< ll , ll >
#define vi vector<int>
#define vvi vector< vi >
const int maxn=(int)(2e5+5);
const ll mod=(ll)(1e9+7);
int a[maxn];
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
int t;cin>>t;
while(t>0)
{
int n;cin>>n;
ll sum=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
sum+=a[i];
}
int res=-1;
for(int i=0;i<n;i++)
{
ll y=sum-a[i];
ll val1=sum*1ll*(n-1),val2=y*n;
if(val1==val2)
{
res=i;break;
}
}
if(res==-1)
{
cout<<"Impossible"<<endl;
}
else
{
cout<<(res+1)<<endl;
}
t--;
}
return 0;
}
Comments are welcome !
