Problem: Mark and Toys

Mark and Jane are very happy after having their first kid. Their son is very fond of toys, so Mark wants to buy some. There are N different toys lying in front of him, tagged with their prices, but he has only $K. He wants to maximize the number of toys he buys with this money.

Now, you are Mark’s best friend and have to help him buy as many toys as possible.

Input Format
The first line will contain two inputs N and K, followed by a line containing N integers separated by a single space indicating the products’ prices.

Output Format
Maximum number of toys Mark can buy for his son.

Constraints
1<=N<=105
1<=K<=109
1<=price of any toy<=109
A toy can’t be bought multiple times.

Sample Input

7 50
1 12 5 111 200 1000 10

Sample Output

4

Explanation

He can buy only 4 toys at most. These toys have the following prices: 1,12,5,10.
Hint (Java code):

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

public class Solution {
private static int N,K;
private static int[] toys;
private static Scanner input;
private static int numberOfToysCanBuy = 0;

public static void main(String[] args){
input = new Scanner(System.in);
N = input.nextInt();
K = input.nextInt();
toys = new int[N];
for(int count = 1; count <= N; ++count)
toys[count-1] = input.nextInt();
Arrays.sort(toys);
for(int count = 0; count < toys.length; ++count){
K -= toys[count];
if(K < 0)
break;
numberOfToysCanBuy++;
}
System.out.println(numberOfToysCanBuy);
}
}

Advertisements