Maximum Number of Products to Buy - Atlassian IIT Roorkee Online Assessment OA

Problem Preview

"### Problem Alice is shopping at Ozone Galleria Mall, where each cubicle sells products at a fixed price. The cubicles are arranged so that prices are in non-decreasing order from left to right. There is an array of n integers, prices, where prices[i] is the price at the i-th cubicle, and q queries to process. For each query, you are given: * pos: Alex's initial position * amount: the amount of money Alex has Alex visits each cubicle from position pos to n and can purchase a maximum of one product from each cubicle visited. The goal is to determine the maximum number of products Alex can buy without exceeding the available amount. ### Input - An array of integers representing the prices of products in each cubicle - A list of queries, where each query contains Alex's initial position and the amount of money Alex has ### Output - The maximum number of products Alex can buy for each query ### Example - n = 5 - prices = [3, 4, 5, 5, 7] - q = 3 - queries = [[2, 10], [1, 24], [5, 5]] ### Queries: 1. pos = 2, amount = 10: Alex visits cubicles 2 through 5 and can buy at most 2 products. Alex can either buy from: - Cubicles 2 and 3: 4 + 5 = 9 (<= 10) - Cubicles 2 and 4: 4 + 5 = 9 (<= 10) - Cubicles 3 and 4: 5 + 5 = 10 (<= 10) The answer is 2. 2. pos = 1, amount = 24: Alex visits all cubicles and can buy from all of them since the total cost is 3 + 4 + 5 + 5 + 7 = 24 (<= 24). The answer is 5. 3. pos = 5, amount = 5: Alex can only visit cubicle 5 but cannot make any purchase since the price (7) exceeds the available amount (5). The answer is 0. ### Hint : Prefix sums and binary search"