Skip to main content
Talentd

Maximum Number of Alloys - Solution & Explanation

MediumArrayBinary Search13 min readAsked at: Microsoft, Uber, Mathworks +1
Practice this problem

Problem Statement

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 <= 100
  • 0 <= budget <= 108
  • composition.length == k
  • composition[i].length == n
  • 1 <= composition[i][j] <= 100
  • stock.length == cost.length == n
  • 0 <= stock[i] <= 108
  • 1 <= cost[i] <= 100

Approach Overview

Problem 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 1: Binary Search with Simulation

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Greedy Simulation Approach

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.

Code

C

C

Complexity

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)

Try this approach in the editor →

Approach 3: Binary Search

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy SimulationO(k * n * X)O(1)Useful for understanding the cost calculation or when the maximum alloy count is very small.
Binary Search with SimulationO(k * n * logX)O(1)Best general solution. Efficient for large budgets or large answer ranges due to logarithmic search.

Video Solution

🔴 2861. Maximum Number of Alloys II Weekly Contest 363 II Binary Search II Leetcode 2861 • Aryan Mittal • 2,679 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Number of Alloys easy or hard?
Maximum Number of Alloys is considered a medium difficulty problem. The main challenge is recognizing that the answer can be binary searched and implementing the feasibility simulation correctly.
Maximum Number of Alloys Python/Java solution
Python and JavaScript implementations typically use binary search combined with a helper function that calculates the purchase cost for producing x alloys. The helper iterates through the metals array and sums deficits multiplied by their costs.
How to solve Maximum Number of Alloys in O(n)?
The full problem cannot generally be solved in strict O(n) time because you must evaluate multiple machines and potential alloy counts. The closest practical optimization is binary search with simulation, which reduces the search space to logarithmic checks while scanning the metals array each time.
What is the best approach for Maximum Number of Alloys?
Binary search with simulation is the most efficient approach. The number of alloys forms a monotonic search space, so you can binary search the maximum feasible value and verify it by calculating the required metal cost for each machine. This runs in O(k * n * logX) time.
Is Maximum Number of Alloys asked at Google/Amazon/Meta?
Problems involving binary search on the answer and resource budgeting frequently appear in interviews at companies like Amazon, Google, and Meta. This problem specifically tests recognizing monotonic feasibility and implementing an efficient check.
What data structure is used in Maximum Number of Alloys?
The solution primarily uses arrays to store machine compositions, metal stock, and metal costs. The algorithm iterates through these arrays to compute deficits and purchasing costs during feasibility checks.
What is the time complexity of Maximum Number of Alloys?
The optimal solution runs in O(k * n * logX) time, where k is the number of machines, n is the number of metal types, and X is the search range of possible alloys. Each binary search step simulates the metal cost calculation in O(n) time for every machine.

Ready to solve this problem?

Practice Maximum Number of Alloys with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays