# Chef and Fixed Deposits MINFD Solution Codechef

## Chef and Fixed Deposits MINFD Solution

Chef wants to make a purchase. For this, he needs X gold coins, but he has none at the moment. Chef has N fixed deposits, the ith of which is worth Ai coins. He wants to open the minimum number of these deposits so that he has at least X coins.

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

Input Format

• The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains two space-separated integers — N and X, as described in the statement.
• The second line of each test case contains N space-separated integers — the ith of which is Ai.

Output Format

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

Constraints

• 1≤T,Ai,N≤100
• 1≤X≤104

Subtask #1 (100 points): Original constraints

Sample Input 1

``````4
4 6
4 3 5 1
3 15
1 5 3
2 5
10 3
4 7
1 2 3 4``````

Sample Output 1

``````2
-1
1
2``````

Explanation

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

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

### 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")``````