Sample Problem: Purchasing maximum items in Java

Problem: You are given the cost of N items and a value sum. The task is to find the maximum number of items that can be purchased using the given sum.

Example:

Input:

costs[] = {1, 12, 5, 111, 200}, sum = 10

Output:

2

Input:

costs[] = {20, 10, 5, 30, 100}, sum = 35

Output:

3

Solution:

One way to approach this problem is to create a min-heap of the cost array. Since we need to find the maximum number of items that can be purchased within the given sum, we can extract items from the constructed min-heap one by one. For each item extracted, we can subtract its value from the sum and increment the count simultaneously. This process can be continued until the sum becomes negative or the heap becomes empty.

In Java, we can create a min-heap using Priority Queue. Here is the implementation:

import java.util.*;

public class PurchaseMaxItems {

static int purchaseMax(List<Integer> items, int sum) {

    PriorityQueue<Integer> pq = new PriorityQueue<Integer>(items);

    

    int res = 0;

    

    while(sum >= 0 && !pq.isEmpty() && pq.peek() <= sum) {

        sum -= pq.poll();

        res++;

    }

    

    return res;

}

public static void main(String[] args) {

    Integer[] costs = {1, 12, 5, 111, 200};

    List<Integer> items = Arrays.asList(costs);

    int sum = 10;

    

    System.out.println(purchaseMax(items, sum)); // Output: 2

} 

}

Output:

2

Time Complexity: The time complexity of this solution is O(N*logN) since it involves creating a min-heap of the cost array.

Auxiliary Space: The auxiliary space required by this solution is O(N) since we are using a Priority Queue to store the items.