Chef and Party Codechef Solution: Tonight, Chef would like to hold a party for his NN friends.
All friends are invited and they arrive at the party one by one in an arbitrary order. However, they have certain conditions — for each valid ii, when the ii-th friend arrives at the party and sees that at that point, strictly less than AiAi other people (excluding Chef) have joined the party, this friend leaves the party; otherwise, this friend joins the party.
Help Chef estimate how successful the party can be — find the maximum number of his friends who could join the party (for an optimal choice of the order of arrivals).
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 containing one integer — the maximum number of Chef’s friends who could join the party.
Constraints
- 1≤T≤1,0001≤T≤1,000
- 1≤N≤1051≤N≤105
- the sum of NN over all test cases does not exceed 106106
Sample Input 1
3 2 0 0 6 3 1 0 0 5 5 3 1 2 3
Sample Output 1
2 4
Explanation
Example case 1: Chef has two friends. Both of them do not require anyone else to be at the party before they join, so they will both definitely join the party.
Example case 2: At the beginning, friends 33 and 44 can arrive and join the party, since they do not require anyone else to be at the party before they join. After that, friend 22 can arrive; this friend would see that there are two people at the party and therefore also join. Then, friend 11 will also join, so in the end, there would be 44 people attending the party.
Example case 3: No one will attend the party because each of Chef’s friends will find zero people at the party and leave, regardless of the order in which they arrive.
Chef and Party CodeChef Solution in JAVA
import java.util.*; class Chef_and_Party { public static void main(String[] args) { Scanner input = new Scanner(System.in); int t = input.nextInt(); while(t-- > 0) { int n = input.nextInt(); int arr[] = new int[n]; for (int i = 0 ; i < n ; i++) { arr[i] = input.nextInt(); } int ans = 0; Arrays.sort(arr); for (int i = 0 ; i < n ; i++) { if (ans >= arr[i]) { ans++; } } System.out.println(ans); } input.close(); } }
Chef and Party CodeChef Solution in CPP
#include <bits/stdc++.h> using namespace std; #define FASTIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define ll long long int #define maxii INT_MAX #define minii INT_MIN #define mod 1000000007 int main() { FASTIO; int t,k; cin>>t; while(t--){ int n,count=0; cin>>n; vector<int> v; for(int i=0;i<n;i++){ cin>>k; v.push_back(k); } sort(v.begin(),v.end()); for(int i=0;i<n;i++){ if(count>=v[i]) count++; } cout<<count<<"\n"; } return 0; }
Chef and Party CodeChef Solution in Python
t=int(input()) while(t!=0): t-=1 n=int(input()) a=list(map(int,input().split())) a=sorted(a) new=[] for i in a: if(len(new)>=i): new.append(i) print(len(new))
Disclaimer: The above Problem (Chef and Party ) is generated by CodeChef but the solution is provided by Chase2learn.This tutorial is only for Educational and Learning purpose.