Chef And Fixed Deposits MINFD Solution Codechef

Page Contents

Codechef Chef and Fixed Deposits MINFD Solution

Chef wants to make a purchase. For this, he needs XX gold coins, but he has none at the moment.

Chef has NN fixed deposits, the ithith of which is worth AiAi coins. He wants to open the minimum number of these deposits so that he has at least XX coins.

You have to tell Chef the minimum number of fixed deposits he must open in order to have XX coins, or say that this is impossible.

Input Format

The first line of 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 two space-separated integers — NN and XX, as described in the statement.
The second line of each test case contains NN space-separated integers — the ithith of which is AiAi.

Output Format

For each test case, output one line containing the answer — the minimum number of FDs Chef must open to have at least XX coins. If it is not possible for him to open FDs such that he has at least XX coins, output −1−1.

Constraints

1≤T,Ai,N≤1001≤T,Ai,N≤100
1≤X≤1041≤X≤104

Subtasks

Subtask #1 (100 points): Original constraints

Sample Input 1

Sample Output 1

Explanation

Test case 11: Chef can open the first and second FDs to get 4+3=74+3=7 coins.

Test case 22: No matter which FDs Chef opens, he cannot have ≥15≥15 coins, so the answer is −1−1.

Click Below for solution

Solution

Program: Chef and Fixed Deposits MINFD Solution in C++

#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
for(int i=0;i<t;i++){
   int n,x;
   int count=0;
   int sum=0;
   cin>>n>>x;
   bool f = false;
   int arr[n];
   for(int j=0;j<n;j++){
       cin>>arr[j];
   }
   sort(arr,arr+n);
   for(int b=(n-1);b>=0;b--){
       count++;
       sum = sum+arr[b];
       if(sum>=x){
           f = true;
           break;
       }
   }
   if(f){
       cout<<count<<endl;
   }
   else{
       cout<<"-1"<<endl;
   }
    }

	return 0;
}

Program: Chef and Fixed Deposits MINFD Solution in Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
	    Scanner inp = new Scanner(System.in);
	    int t = inp.nextInt();
	    for(;t>0;t--){
	        int n,x;
	        n = inp.nextInt();
	        x = inp.nextInt();
	        
	        int arr[] = new int[n];
	        int sum = 0;
	        for(int i=0;i<n;i++){
	            arr[i]=inp.nextInt();
	            sum+=arr[i];
	        }
	        
	        if(x>sum){
	           System.out.println(-1);
	        }else{
	            Arrays.sort(arr);
	            int count=0,ind=n-1;
	            while(x>0){
	                x=x-arr[ind];
	                ind--;
	                count++;
	            }
	            System.out.println(count);
	        }
	    }
	}
}

Program: Chef and Fixed Deposits MINFD Solution in Python

for _ in range(int(input())):
    n,d=input().split()
    n=int(n)
    d=int(d)
    a=list(map(int,input().split()))
    a.sort()
    a.reverse()
    s=sum(a)
    if s>=d:
        if d in a:
            print("1")
        elif d<max(a):
            print("1")
        else:
            su=a[0]
            c=0
            for i in range(1,n):
                if c==1:
                    break
                su=su+a[i]
                if su==d or su>d:
                    print(i+1)
                    #print(a[i])
                    c=c+1
                
    else:
        print("-1")

Chef and Fixed Deposits MINFD Solution Codechef