Find the largest capacity you can choose without exceeding a given budget.
Problem
You are given a list of candidate capacities and a budget limit. Choosing a capacity may incur a cost determined by the input data and the chosen value. Your task is to determine the maximum capacity that can be selected while keeping the total cost within the budget.
This is a typical maximize-the-answer under a constraint problem: larger capacities are better, but they become invalid once the cost goes above the allowed budget.
Goal
Return the greatest feasible capacity value.
Notes
- If no positive capacity is feasible, return the smallest valid fallback according to the problem's rules.
- The key challenge is efficiently checking whether a candidate capacity is affordable.
- A direct search over all values may be too slow, so an optimized monotonic search strategy is usually expected.
Input Format
- The first line contains an integer
n, the number of candidate values. - The second line contains
nintegers describing the available capacities or capacity-related values. - The third line contains an integer
budget.
The exact cost function depends on the chosen capacity, but it is monotonic with respect to the capacity: if a capacity is feasible, then all smaller capacities are also feasible.
Output Format
- Return a single integer: the maximum feasible capacity within budget.
Constraints
1 <= n <= $10^{5}$- Values are integers.
- The feasibility check is monotonic in the chosen capacity.
- Time complexity should be better than linear scanning over all possible capacities when the search space is large.
Example 1
Input
n = 5 values = [2, 3, 5, 7, 11] budget = 10
Output
7
Explanation
A capacity of 7 is still affordable, while a larger choice would exceed the budget under the problem's monotonic cost rule. Therefore, 7 is the maximum feasible capacity.
Example 2
Input
n = 4 values = [1, 4, 6, 8] budget = 3
Output
1
Explanation
Only the smallest capacity remains feasible within the budget. Since larger capacities would increase the cost beyond the limit, the answer is 1.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.