Chocolate Monger Codechef Solution

There are nn chocolates, and you are given an array of nn numbers where the ii-th number AiAi is the flavour type of the ii-th chocolate. Sebrina wants to eat as many different types of chocolates as possible, but she also has to save at least xx number of chocolates for her little brother.

Find the maximum possible number of distinct flavour types Sebrina can have.

Input:

The first line contains an integer TT — the number of test cases.

The first line of each test case consists of two integers nn, xx – The number of chocolates Sabrina has and the number of chocolates she has to save for her brother, respectively.

The second line contains nn integers A1,…,AnA1,…,An, where the ii-th chocolate has type AiAi.

Output:

For each test case, output a single integer denoting the maximum possible number of distinct chocolate flavours Sabrina can eat.

Constraints

1≤T≤101≤T≤10

1≤x≤n≤2⋅1051≤x≤n≤2⋅105

1≤Ai≤1091≤Ai≤109

Sum of nn over all test cases do not exceed 2⋅1052⋅105

Sample Input 1 

3
2 1
1 2
4 2
1 1 1 1
5 3
50 50 50 100 100

Sample Output 1 

1
1
2

Explanation

In the first test case, she can give any 1 chocolate to her brother and can have the other for herself resulting in 1 flavour type for Sebrina.

Chocolate Monger   – CodeChef Solution in JAVA

import java.util.Arrays;
import java.util.Scanner;

class CodeChef {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long T = sc.nextLong();
        while (T-- != 0) {
           long n = sc.nextLong();
           long x = sc.nextLong();
           long arr[] = new long[(int) n];
           long z = n-x;
           long eat=0;
           long count=0;
           for(int o=0;o<n;o++){
               arr[o] = sc.nextLong();
           }
            Arrays.sort(arr);
           for(int i=0;i<n-1;i++) {
               if(arr[i]==arr[i+1]){
                   arr[i]=0;
               }
           }
           for(int j=0;j<n;j++){
               if(arr[j]!=0){
                   count++;
               }
           }
                System.out.println(Math.min(count,z));

        }
    }


}

Chocolate Monger – CodeChef Solution in CPP

#include <bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(int i=a;i<b;i++) 
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        int n,x;
        cin>>n>>x;
        unordered_set<int> us;
        int a;
        For(i,0,n){
            cin>>a;
            us.insert(a);
        }
        if(us.size()<n-x) cout<<us.size()<<endl;
        else cout<<n-x<<endl;
        
    }
    return 0;
}

Chocolate Monger   -CodeChef Solution in Python

t=int(input())
for i in range(t):
    n,x=map(int,input().split())
    list1=list(map(int,input().split()))
    dic={}
    for j in list1:
        if j in dic.keys():
            if(x>0):
                x=x-1
        else:
            dic[j]=x-1
    print(len(dic)-x)
                

Disclaimer: The above Problem (Chocolate Monger  ) is generated by CodeChef but the solution is provided by Codeworld19.This tutorial is only for Educational and Learning purpose.

Leave a Reply

Your email address will not be published. Required fields are marked *