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
Subtasks
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")