Places visitable per price segment within budget

Problem Given price segments, e.g. prices = {100, 50, 25, 10, 5}, and a total budget, return how many places from each price segment can be visited so that the leftover budget is minimized.

Input / Output

• Input: int array prices (segment costs), int budget.
• Output: count per segment, minimizing the unspent remainder.

Constraints

• Clarify whether counts are unbounded per segment (coin-change style) or one place per segment; both variants should be discussed.

Example

• prices = {100, 50, 25, 10, 5}, budget = 190 → e.g. 1×100 + 1×50 + 1×25 + 1×10 + 1×5 = 190, leftover 0 → counts [1,1,1,1,1].

Expected approach

• If any denomination structure is "canonical" (like the example, where greedy is safe), take each price from largest to smallest: count = remaining / price, remaining %= price — O(n). For arbitrary prices greedy fails; use coin-change DP over the budget (dp[amount] = reachable/max spend), then backtrack the counts — O(n * budget). Explaining when greedy breaks (e.g. {9, 6, 5} with budget 11) is the key discussion point.