Chef and Mean Codechef Solution

Chef and Mean Codechef Solution: 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  Chase2learn.This tutorial is only for Educational and Learning purpose.

Leave a Comment