Watch 10 video solutions for Maximum Number of Alloys, a medium level problem involving Array, Binary Search. This walkthrough by Aryan Mittal has 2,598 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are the owner of a company that creates alloys using various types of metals. There are n different types of metals available, and you have access to k machines that can be used to create alloys. Each machine requires a specific amount of each metal type to create an alloy.
For the ith machine to create an alloy, it needs composition[i][j] units of metal of type j. Initially, you have stock[i] units of metal type i, and purchasing one unit of metal type i costs cost[i] coins.
Given integers n, k, budget, a 1-indexed 2D array composition, and 1-indexed arrays stock and cost, your goal is to maximize the number of alloys the company can create while staying within the budget of budget coins.
All alloys must be created with the same machine.
Return the maximum number of alloys that the company can create.
Example 1:
Input: n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,0], cost = [1,2,3] Output: 2 Explanation: It is optimal to use the 1st machine to create alloys. To create 2 alloys we need to buy the: - 2 units of metal of the 1st type. - 2 units of metal of the 2nd type. - 2 units of metal of the 3rd type. In total, we need 2 * 1 + 2 * 2 + 2 * 3 = 12 coins, which is smaller than or equal to budget = 15. Notice that we have 0 units of metal of each type and we have to buy all the required units of metal. It can be proven that we can create at most 2 alloys.
Example 2:
Input: n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,100], cost = [1,2,3] Output: 5 Explanation: It is optimal to use the 2nd machine to create alloys. To create 5 alloys we need to buy: - 5 units of metal of the 1st type. - 5 units of metal of the 2nd type. - 0 units of metal of the 3rd type. In total, we need 5 * 1 + 5 * 2 + 0 * 3 = 15 coins, which is smaller than or equal to budget = 15. It can be proven that we can create at most 5 alloys.
Example 3:
Input: n = 2, k = 3, budget = 10, composition = [[2,1],[1,2],[1,1]], stock = [1,1], cost = [5,5] Output: 2 Explanation: It is optimal to use the 3rd machine to create alloys. To create 2 alloys we need to buy the: - 1 unit of metal of the 1st type. - 1 unit of metal of the 2nd type. In total, we need 1 * 5 + 1 * 5 = 10 coins, which is smaller than or equal to budget = 10. It can be proven that we can create at most 2 alloys.
Constraints:
1 <= n, k <= 1000 <= budget <= 108composition.length == kcomposition[i].length == n1 <= composition[i][j] <= 100stock.length == cost.length == n0 <= stock[i] <= 1081 <= cost[i] <= 100Problem Overview: You are given multiple machines that can produce alloys using different metal compositions. Each metal has limited stock and a purchase cost. With a fixed budget, determine the maximum number of alloys you can manufacture using exactly one machine.
Approach 1: Greedy Simulation Approach (O(k * n * X) time, O(1) space)
The direct way is to simulate alloy production machine by machine. For each machine, repeatedly attempt to produce one more alloy and calculate the additional metals required beyond the available stock. If extra metals are needed, multiply the deficit by the corresponding cost and subtract it from the budget. Stop once the budget becomes negative. The total alloys produced before exceeding the budget is the result for that machine. This approach uses straightforward iteration over metals for each alloy produced. While easy to implement, the repeated simulation can become slow when the possible alloy count is large.
Approach 2: Binary Search with Simulation (O(k * n * logX) time, O(1) space)
A more scalable strategy treats the answer as a search space. Instead of producing alloys one by one, you binary search the maximum number of alloys x. For a candidate value x, compute how much additional metal each machine needs: required = max(0, composition[i] * x - stock[i]). Multiply the deficit by the metal's cost and sum it across all metals. If the total cost stays within the budget, producing x alloys with that machine is feasible. Check every machine and accept the candidate if any machine satisfies the constraint. If feasible, move the binary search right; otherwise move left.
The key insight: feasibility is monotonic. If producing x alloys is affordable, any smaller number is also affordable. That monotonic property makes binary search the optimal strategy. Each feasibility check only scans the metals array once, making the check efficient.
The algorithm iterates through machines, simulates required purchases using simple arithmetic on arrays, and keeps the maximum feasible result. Since the data is naturally represented using arrays of compositions, stock, and cost, understanding basic array traversal is enough for implementation.
Recommended for interviews: Binary Search with Simulation is the expected solution. The greedy simulation demonstrates the core feasibility calculation, but the optimized version shows you recognize the monotonic search space and apply binary search to reduce the complexity from linear growth to logarithmic checks.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Simulation | O(k * n * X) | O(1) | Useful for understanding the cost calculation or when the maximum alloy count is very small. |
| Binary Search with Simulation | O(k * n * logX) | O(1) | Best general solution. Efficient for large budgets or large answer ranges due to logarithmic search. |