Maximum Number Of Alloys
01 · Problem
A factory produces alloys from n kinds of metal using one of k machines.
composition[i][j]is how many units of metaljmachineiconsumes to produce one alloy.stock[j]is how many units of metaljyou already own.cost[j]is the price of buying one additional unit of metalj.budgetis the total amount of money you can spend on buying extra metal.
You must choose exactly one machine and produce all alloys with it. Return the maximum number of alloys you can produce without spending more than budget. The answer may be 0.
02 · Examples
n = 2, k = 2, budget = 20, composition = [[1,2],[3,1]], stock = [2,0], cost = [2,3]
3
Machine 0 makes 3 alloys by buying 1 unit of metal 0 (cost 2) and 6 units of metal 1 (cost 18), total 20. Machine 1 can make at most 2 alloys, because 3 alloys would cost 23.
n = 3, k = 1, budget = 7, composition = [[2,1,1]], stock = [4,2,0], cost = [1,1,2]
2
For 2 alloys the stock covers metals 0 and 1, so only 2 units of metal 2 are bought for 4. A third alloy would cost 2 + 1 + 6 = 9, which is over budget.
n = 2, k = 3, budget = 10, composition = [[2,1],[1,2],[1,1]], stock = [1,1], cost = [5,5]
2
Machine 2 uses one unit of each metal per alloy: 2 alloys need 2 of each, so buy 1 of each for 10. Machines 0 and 1 can make at most 1 alloy each. Best is 2.
03 · Constraints
- 011 <= n, k <= 100
- 020 <= budget <= 108
- 03composition.length == k and composition[i].length == n
- 041 <= composition[i][j] <= 100
- 05stock.length == cost.length == n, 0 <= stock[j] <= 108, 1 <= cost[j] <= 100
04 · Optimal complexity
- Time
- O(k * n * log(budget + max(stock)))
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.