Hello Programmers In this post, you will know how to solve the Chef and Mean Codechef Solution.
One more thing to add, don’t directly look for the solutions, first try to solve the problems of Codechef by yourself. If you find any difficulty after trying several times, then you can look for solutions.
Problem
Chef has invested his savings into NN coins (numbered 11 through NN). For each valid ii, the ii-th coin has value AiAi. Chef does not want to know how much money he has, so he remembers the mean value of the coins instead of the sum of their values.
A waiter from Chef’s restaurant plans to steal exactly one of Chef’s coins, but he does not want Chef to know about this, so he can only steal a coin if the arithmetic mean of all remaining coins is the same as the original arithmetic mean of all coins. Since the waiter is not good at mathematics, can you help him complete his plan?
You have to determine whether it is possible to steal some coin and if it is possible, choose the coin the waiter should steal. If there are multiple coins that can be stolen, choose the one with the smallest number.
Input
- The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
- The first line of each test case contains a single integer NN.
- The second line contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.
Output
For each test case, print a single line. If the waiter cannot steal any coin, this line should contain the string "Impossible" (without quotes). Otherwise, it should contain the number of the coin he should steal.
Constraints
- 1≤T≤101≤T≤10
- 2≤N≤1052≤N≤105
- 1≤Ai≤1091≤Ai≤109 for each valid ii
Sample Input 1
3 5 1 2 3 4 5 4 5 4 3 6 10 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 1
3 Impossible 1
Explanation
Example case 1: Stealing the third coin does not change the mean. Initially, it is (1+2+3+4+5)/5=3(1+2+3+4+5)/5=3 and after stealing this coin, it is still (1+2+4+5)/4=3(1+2+4+5)/4=3.
Example case 2: It is not possible to steal any coin without changing the mean.
Example case 3: The mean is always 109109, both initially and after removing any coin, so each coin can be stolen. In that case, we should choose the first coin.
Chef and Mean CodeChef Solution in JAVA
import java.util.Scanner;
class chef_mean {
public static void main(String[]args) {
Scanner input = new Scanner(System.in);
int t = input.nextInt();
while(t-- > 0) {
int n = input.nextInt();
long arr[] = new long[n];
long sum = 0;
for (int i = 0 ; i < n ; i++) {
arr[i] = input.nextLong();
sum += arr[i];
}
if (sum % n != 0) {
System.out.println("Impossible");
continue;
}
long Mean = sum / n;
int found = -1;
for (int i = 0 ; i < n ; i++) {
if ((sum - arr[i]) % (n-1) != 0) {
continue;
}
if (((sum - arr[i]) / (n-1)) == Mean) {
found = i+1;
break;
}
}
if (found != -1) {
System.out.println(found);
} else {
System.out.println("Impossible");
}
}
input.close();
}
}Chef and Mean CodeChef Solution in CPP
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define forn(i,n) for(int i=0;i<n;i++)
#define ff first
#define ss second
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define mii map<int,int>
#define pqb priority_queue<int>
#define pqs priority_queue<int,vi,greater<int> >
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define leadingzr(x) __builtin_clz(x)
#define mod 1000000007
#define inf 1e18
#define ps(x,y) fixed<<setprecision(y)<<x
#define mk(arr,n,type) type *arr=new type[n];
#define arr(a,n) int n;cin>>n;vector<int> a(n);for(int i=0;i<n;i++) cin>>a[i];
#define w(x) int x; cin>>x; while(x--)
#define conarr(a,n,k) int n,k;cin>>n>>k;vector<int> a(n);for(int i=0;i<n;i++) cin>>a[i];
#define range(x) (x).begin(),(x).end()
#define endl "\n"
#define total(x) accumulate(x.begin(),x.end(),(int)0)
#define prefix(a,n) vector<int> prefix(n);prefix[0]=a[0];for(int i=1;i<n;i++) prefix[i]=prefix[i-1]+a[i];
#define suffix(a,n) vector<int> suffix(n);suffix[n-1]=a[n-1];for(int i=n-2;i>=0;i--) suffix[i]=suffix[i+1]+a[i];
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> pbds;
int add(int x,int y) {int res=x+y; return (res>=mod ? res-mod: res);}
int mul(int x,int y) {int res=x*y; return (res>=mod? res%mod : res);}
int sub(int x,int y) {int res=x-y; return (res<0?res+mod:res);}
int power(int x,int y) {int res=1; x%=mod; while(y){ if(y&1) res=mul(res,x); y>>=1; x=mul(x,x);} return res;}
int mod_inv(int x) {return power(x,mod-2);}
void hkv()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt","w", stderr);
#endif
}
//-----------debugging-------------
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(long double t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(unsigned long long t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(unordered_set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(unordered_map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
//--------------------------------
/*
----------Rough Work----------
*/
void solve(){
arr(a,n);
int sum=total(a);
if(sum%n){
cout<<"Impossible"<<endl;
return;
}
int x=sum/n;
for(int i=0;i<n;i++){
if(a[i]==x){
cout<<i+1<<endl;
return;
}
}
cout<<"Impossible"<<endl;
}
int32_t main()
{
hkv();
// solve();
w(t) solve();
return 0;
}Chef and Mean CodeChef Solution in Python
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
b=sum(a)/n
if(b in a):
print(a.index(b)+1)
else:
print('Impossible')Disclaimer: The above Problem (Chef and Mean ) is generated by CodeChef but the solution is provided by BrokenProgrammers. This tutorial is only for Educational and Learning purpose.
Note:- I compile all programs, if there is any case program is not working and showing an error please let me know in the comment section. If you are using adblocker, please disable adblocker because some functions of the site may not work correctly.