Problem Link - CafeLuxe Budget
Problem Statement:
The chef is an avid traveler who enjoys visiting different cafes around the city to try their specialty coffee, “CafeLuxe.” There are n different cafes where he can buy his favorite coffee, and the price of a cup in the i-th cafe is x[i] rupees. The chef has planned to treat himself to a cup of “CafeLuxe” for q consecutive days. He knows that on the i-th day, he will have m[i] rupees available to spend. For each day, Chef wants to find out how many different cafes he can afford to buy a cup of “CafeLuxe.”
Approach:
To solve this problem, we start by sorting the list of item prices. Sorting helps us quickly determine how many items are affordable for each budget using a method called binary search. Binary search allows us to find out where the prices exceed the budget, making it easier to count the items that fit within that budget.
After sorting the prices, we look at each budget and use binary search to count how many prices are less than or equal to that budget. Alternatively, we can use a built-in function that directly shows us the position of the first price that is higher than the budget, helping us count the affordable items quickly.
Step-by-step process:
-
Input the Prices:
Start by reading the number of item prices and the prices themselves. -
Sort the Prices:
Next, sort the prices in ascending order. This way, we can easily find out how many items are cheaper than or equal to each budget. -
Input the Budgets:
Read the number of budgets and the budgets themselves. -
Count Affordable Items:
For each budget, use binary search to find out how many items can be bought. This search will help identify which prices are within the budget. -
Output the Results:
Finally, for each budget, print the number of items that can be purchased.
Time Complexity:
O(n log n + q log n), where n is the number of prices (due to sorting) and q is the number of budgets (for counting).
Space Complexity:
O(n) for storing the prices and budgets.