Round A 2020 Google Kick Start Allocation Problem| JAVA | Know About

Problem

There are N houses for sale. The i-th house costs Ai dollars to buy. You have a budget of B dollars to spend.

What is the maximum number of houses you can buy?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a single line containing the two integers N and B. The second line contains N integers. The i-th integer is Ai, the cost of the i-th house.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum number of houses you can buy.

In Sample Case #1, you have a budget of 100 dollars. You can buy the 1st and 3rd houses for 20 + 40 = 60 dollars.
In Sample Case #2, you have a budget of 50 dollars. You can buy the 1st, 3rd and 4th houses for 30 + 10 + 10 = 50 dollars.
In Sample Case #3, you have a budget of 300 dollars. You cannot buy any houses (so the answer is 0).


PROGRAM

Sort all the houses by prices from low to high using Arrays.sort() and then buy houses one by one until we run out of money.

import java.io.*; import java.util.*; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(new BufferedReader(new InputStreamReader(System.in))); int t = sc.nextInt(); for (int i = 1; i <= t; i++) { int N, count = 0, A = 0; N = sc.nextInt(); int B = sc.nextInt(); int[] price = new int[N]; for (int j = 0; j < N; j++) { price[j] = sc.nextInt(); } Arrays.sort(price); for (int l = 0; l < N; l++) { A += price[l]; if (A == B) count++; if (A >= B) break; count++; } System.out.printf("Case #%d: %d\n", i, count); } } }

Here is the link for Google KickStart Round A 2020 Plates problem using JAVA.