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.
This approach considers maximum potential units of alloys we can produce using binary search over the number of alloys. For each possible number of alloys in the search space, we simulate the verification: we calculate the total cost needed, considering the metal composition and available stock. If the cost is within the budget, we attempt more alloys, otherwise, we reduce the count.
The Python solution uses a binary search approach to maximize the number of alloys produced. We iterate over each machine to evaluate the maximum possible number of alloys that can be produced with the given budget. The binary search checks the feasibility of producing a specific number of alloys and adjusts based on whether the calculated cost is within the budget limits.
Python
JavaScript
Time Complexity: O(k * log(max_possible_alloys) * n) where max_possible_alloys is a heuristic upper bound.
Space Complexity: O(1) since it uses constant extra space.
This approach uses a greedy strategy for each machine. It computes the number of alloys directly by going through each metal type and simulates the cost accumulation based on the composition needs. The aim is to reach the maximum number directly without extensive binary search, ensuring we don't exceed the budget.
This C implementation of a greedy approach iterates over each machine, progressively calculating the total cost to determine the number of alloys while remaining within the budget. It checks each possible increase in the number of alloys one by one, adjusting based on metal requirements.
C
Time Complexity: O(n * k * budget/cost_min) where cost_min is the minimum cost of any metal per unit. It's less optimal for larger budgets.
Space Complexity: O(1)
We note that all alloys need to be made by the same machine, so we can enumerate which machine to use to make the alloy.
For each machine, we can use binary search to find the maximum integer x such that we can use this machine to make x alloys. The maximum of all x is the answer.
The time complexity is O(n times k times log M), where M is the upper bound of the binary search, and in this problem, M leq 2 times 10^8. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Binary Search with Simulation | Time Complexity: O(k * log(max_possible_alloys) * n) where max_possible_alloys is a heuristic upper bound. Space Complexity: O(1) since it uses constant extra space. |
| Greedy Simulation Approach | Time Complexity: O(n * k * budget/cost_min) where cost_min is the minimum cost of any metal per unit. It's less optimal for larger budgets. Space Complexity: O(1) |
| Binary Search | — |
| 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. |
🔴 2861. Maximum Number of Alloys II Weekly Contest 363 II Binary Search II Leetcode 2861 • Aryan Mittal • 2,598 views views
Watch 9 more video solutions →Practice Maximum Number of Alloys with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor