Chef and Fixed Deposits MINFD Solution Codechef

by

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

January Long Challenge 2022 Solution

Leave a Comment

four × 4 =