Most Items Within Budget

Easy

A shop has items whose prices are given in the array prices. Several shoppers come in, each with their own budget budgets[i]. For each shopper, find the largest number of distinct items they can buy without the total exceeding their budget. Each item exists in a single copy, but shoppers do not affect each other: every one of them chooses from the full stock. Return the answers in the same order as budgets.

Example 1

prices=[7, 3, 9, 1], budgets=[4, 12, 100, 2] → [2, 3, 4, 1]

With 4 you buy 1 and 3; with 12 you buy 1, 3 and 7; with 100 everything; with 2 only the item that costs 1.

Example 2

prices=[5, 5, 5], budgets=[14] → [2]

Two items cost 10; a third one no longer fits.

Constraints

1 ≤ len(prices), len(budgets) ≤ 10⁵
1 ≤ prices[i], budgets[i] ≤ 10⁶

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Binary Search Prefix Sum Sorting

Similar problems

Even Out With Increments Medium Flowerbed Beauty on a Budget Hard Rug Over Painted Stretches Medium Common Setting at Different Step Prices Hard Richest Row of Houses Medium

Input

prices=[7, 3, 9, 1], budgets=[4, 12, 100, 2]

Expected

[2, 3, 4, 1]

Run checks the first 3 tests in your browser. Submit checks all 100 tests on the server, hidden ones included.