2861. Maximum Number of Alloys

MediumArrayBinary Search
Leetcode Link

Problem Description

You own a company that produces alloys using different types of metals and machines. Here's the setup:

  • You have n different types of metals available
  • You have access to k machines that can create alloys
  • Each machine has its own "recipe" - it needs specific amounts of each metal type to create one alloy
  • The array composition[i][j] tells you how many units of metal type j the i-th machine needs to make one alloy
  • You start with stock[i] units of metal type i in your inventory
  • If you need more metal, you can buy additional units - one unit of metal type i costs cost[i] coins
  • You have a total budget of budget coins to spend on buying additional metals

Important constraint: All alloys must be created using the same machine. You can't mix and match - if you choose machine 1, all your alloys must be made with machine 1.

Your goal is to determine the maximum number of alloys you can create while staying within your budget.

For example, if a machine needs 2 units of metal A and 3 units of metal B to make one alloy, and you want to make 5 alloys, you'll need 10 units of metal A and 15 units of metal B total. You can use your existing stock first, then buy any additional metals needed as long as you don't exceed your budget.

The function should return the maximum number of alloys that can be created.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

Let's think about what we're trying to find. We want the maximum number of alloys we can make, and we must use exactly one machine for all alloys.

First observation: Since we must pick one machine and stick with it, we need to try each machine separately and see which one gives us the best result. This means we'll iterate through all k machines.

For each machine, the key question becomes: "What's the maximum number of alloys I can make with this specific machine?"

Now, here's the critical insight: If we can make x alloys with a certain budget, then we can definitely make x-1, x-2, ..., 1, or 0 alloys with the same or less budget. Conversely, if we cannot afford to make x alloys, we definitely cannot make x+1, x+2, or more alloys.

This monotonic property is perfect for binary search! We can search for the maximum number of alloys we can make with each machine.

For the binary search bounds:

  • Lower bound: 0 alloys (we can always make zero)
  • Upper bound: We need to be clever here. The theoretical maximum would be limited by either our budget or our existing stock. A reasonable upper bound is budget + stock[0] (or any large enough value).

For each candidate number mid during binary search, we calculate the cost:

  • To make mid alloys with machine i, we need mid * composition[i][j] units of metal type j
  • We already have stock[j] units, so we need to buy max(0, mid * composition[i][j] - stock[j]) additional units
  • The cost for metal type j is max(0, mid * composition[i][j] - stock[j]) * cost[j]
  • Total cost is the sum across all metal types

If the total cost is within budget, we can make mid alloys, so we search for a larger number. Otherwise, we search for a smaller number.

After trying all machines with binary search, we return the maximum number of alloys found across all machines.

Learn more about Binary Search patterns.

Solution Implementation

1class Solution: 2 def maxNumberOfAlloys( 3 self, 4 n: int, 5 k: int, 6 budget: int, 7 composition: List[List[int]], 8 stock: List[int], 9 cost: List[int], 10 ) -> int: 11 def exceeds_budget(machine_composition: List[int], num_alloys: int) -> bool: 12 """ 13 Feasible function for binary search template. 14 Returns True if producing num_alloys EXCEEDS budget (cannot afford). 15 Pattern: False, False, ..., False, True, True, True 16 We find first True (first unaffordable), answer is first_true_index - 1. 17 """ 18 total_cost = sum( 19 max(0, num_alloys * required - available) * unit_cost 20 for required, available, unit_cost in zip(machine_composition, stock, cost) 21 ) 22 return total_cost > budget 23 24 max_alloys = 0 25 26 # Try each machine (each has different composition requirements) 27 for machine_composition in composition: 28 # Binary search for maximum number of alloys this machine can produce 29 # Search space: [0, upper_bound] 30 # Pattern: can_afford=True, True, ..., True, False, False (for original condition) 31 # Inverted: exceeds_budget=False, False, ..., False, True, True 32 # Find first True index (first position that exceeds budget) 33 left, right = 0, budget + stock[0] 34 first_true_index = -1 35 36 while left <= right: 37 mid = left + (right - left) // 2 38 if exceeds_budget(machine_composition, mid): 39 first_true_index = mid 40 right = mid - 1 41 else: 42 left = mid + 1 43 44 # Maximum affordable alloys is first_true_index - 1 45 # If first_true_index is -1, all values in range are affordable 46 if first_true_index == -1: 47 machine_max = budget + stock[0] 48 else: 49 machine_max = first_true_index - 1 50 51 max_alloys = max(max_alloys, machine_max) 52 53 return max_alloys 54
1class Solution { 2 // Instance variables for sharing data between methods 3 private int metalCount; // Number of different metal types 4 private int budget; // Available budget for purchasing metals 5 private List<List<Integer>> composition; // Composition requirements for each machine 6 private List<Integer> stock; // Current stock of each metal type 7 private List<Integer> cost; // Cost per unit of each metal type 8 9 /** 10 * Feasible function for binary search template. 11 * Returns true if producing targetAlloys EXCEEDS budget for ALL machines. 12 * Pattern: false, false, ..., false, true, true, true 13 * We find first true (first unaffordable for all machines). 14 */ 15 private boolean exceedsBudgetForAllMachines(long targetAlloys) { 16 // Try each machine to see if any can produce the target within budget 17 for (List<Integer> machineComposition : composition) { 18 long totalCost = 0; 19 20 // Calculate cost for all metal types needed by this machine 21 for (int metalIndex = 0; metalIndex < metalCount; metalIndex++) { 22 long metalNeeded = Math.max(0, 23 machineComposition.get(metalIndex) * targetAlloys - stock.get(metalIndex)); 24 totalCost += metalNeeded * cost.get(metalIndex); 25 } 26 27 // If this machine can produce within budget, return false (affordable) 28 if (totalCost <= budget) { 29 return false; 30 } 31 } 32 33 // All machines exceed budget 34 return true; 35 } 36 37 /** 38 * Finds the maximum number of alloys that can be produced 39 * using any single machine within the given budget 40 */ 41 public int maxNumberOfAlloys(int n, int k, int budget, 42 List<List<Integer>> composition, 43 List<Integer> stock, 44 List<Integer> cost) { 45 // Initialize instance variables 46 this.metalCount = n; 47 this.budget = budget; 48 this.composition = composition; 49 this.stock = stock; 50 this.cost = cost; 51 52 // Binary search using template: find first true index 53 int left = 0; 54 int right = budget + stock.get(0); 55 int firstTrueIndex = -1; 56 57 while (left <= right) { 58 int mid = left + (right - left) / 2; 59 if (exceedsBudgetForAllMachines(mid)) { 60 firstTrueIndex = mid; 61 right = mid - 1; 62 } else { 63 left = mid + 1; 64 } 65 } 66 67 // Maximum affordable is firstTrueIndex - 1 68 // If firstTrueIndex is -1, all values in range are affordable 69 if (firstTrueIndex == -1) { 70 return budget + stock.get(0); 71 } 72 return firstTrueIndex - 1; 73 } 74} 75
1class Solution { 2public: 3 int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) { 4 // Feasible function: returns true if producing targetAlloys EXCEEDS budget for ALL machines 5 // Pattern: false, false, ..., false, true, true, true 6 auto exceedsBudgetForAllMachines = [&](long long targetAlloys) { 7 for (int machineIndex = 0; machineIndex < k; machineIndex++) { 8 long long totalCost = 0; 9 vector<int>& currentMachineComposition = composition[machineIndex]; 10 11 for (int metalType = 0; metalType < n; metalType++) { 12 long long metalsToBuy = max(0LL, targetAlloys * currentMachineComposition[metalType] - stock[metalType]); 13 totalCost += metalsToBuy * cost[metalType]; 14 } 15 16 // If this machine can produce within budget, return false 17 if (totalCost <= budget) { 18 return false; 19 } 20 } 21 // All machines exceed budget 22 return true; 23 }; 24 25 // Binary search using template: find first true index 26 int left = 0; 27 int right = budget + stock[0]; 28 int firstTrueIndex = -1; 29 30 while (left <= right) { 31 int mid = left + (right - left) / 2; 32 if (exceedsBudgetForAllMachines(mid)) { 33 firstTrueIndex = mid; 34 right = mid - 1; 35 } else { 36 left = mid + 1; 37 } 38 } 39 40 // Maximum affordable is firstTrueIndex - 1 41 if (firstTrueIndex == -1) { 42 return budget + stock[0]; 43 } 44 return firstTrueIndex - 1; 45 } 46}; 47
1/** 2 * Finds the maximum number of alloys that can be created given budget and material constraints. 3 * Uses binary search template to find the optimal number of alloys. 4 */ 5function maxNumberOfAlloys( 6 n: number, 7 k: number, 8 budget: number, 9 composition: number[][], 10 stock: number[], 11 cost: number[], 12): number { 13 /** 14 * Feasible function for binary search template. 15 * Returns true if producing targetAlloys EXCEEDS budget for ALL machines. 16 * Pattern: false, false, ..., false, true, true, true 17 */ 18 const exceedsBudgetForAllMachines = (targetAlloys: number): boolean => { 19 for (const machineComposition of composition) { 20 let totalCost = 0; 21 22 for (let metalIndex = 0; metalIndex < n; metalIndex++) { 23 const requiredUnits = targetAlloys * machineComposition[metalIndex]; 24 const unitsToBuy = Math.max(0, requiredUnits - stock[metalIndex]); 25 totalCost += unitsToBuy * cost[metalIndex]; 26 } 27 28 // If this machine can produce within budget, return false 29 if (totalCost <= budget) { 30 return false; 31 } 32 } 33 34 // All machines exceed budget 35 return true; 36 }; 37 38 // Binary search using template: find first true index 39 let left = 0; 40 let right = budget + stock[0]; 41 let firstTrueIndex = -1; 42 43 while (left <= right) { 44 const mid = Math.floor((left + right) / 2); 45 if (exceedsBudgetForAllMachines(mid)) { 46 firstTrueIndex = mid; 47 right = mid - 1; 48 } else { 49 left = mid + 1; 50 } 51 } 52 53 // Maximum affordable is firstTrueIndex - 1 54 if (firstTrueIndex === -1) { 55 return budget + stock[0]; 56 } 57 return firstTrueIndex - 1; 58} 59

Solution Approach

The solution uses the binary search template to find the maximum number of alloys that can be created within budget.

Understanding the Feasible Pattern:

For this problem, we want to find the maximum number of alloys. The affordability pattern looks like:

  • For 0 alloys: affordable (True)
  • For 1 alloy: affordable (True)
  • ...
  • For k alloys: affordable (True)
  • For k+1 alloys: NOT affordable (False)

To use our template which finds the first True, we invert the condition. Define exceedsBudget(x) as "producing x alloys exceeds budget for ALL machines":

  • Pattern becomes: False, False, ..., False, True, True, True
  • We find the first True index (first unaffordable amount)
  • Maximum affordable = firstTrueIndex - 1

Binary Search Template Applied:

left, right = 0, budget + stock[0] first_true_index = -1  while left <= right:  mid = left + (right - left) // 2  if exceeds_budget(mid): # feasible condition  first_true_index = mid  right = mid - 1  else:  left = mid + 1  return first_true_index - 1 if first_true_index != -1 else upper_bound

Cost Calculation:

For each candidate mid alloys, we check if ANY machine can produce within budget:

total_cost = sum(max(0, mid * required - available) * unit_cost  for required, available, unit_cost in zip(composition, stock, cost)) return total_cost > budget # True if exceeds budget
  • mid * required: total units needed of this metal type
  • max(0, mid * required - available): additional units to buy after using stock
  • Multiply by unit cost and sum across all metals

Why This Works:

The key insight is that cost is monotonically increasing with the number of alloys. More alloys always cost at least as much as fewer alloys. This creates the clear boundary we need for binary search.

After finding the first unaffordable amount, we return firstTrueIndex - 1 as the maximum affordable number of alloys.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Example:

  • n = 2 metal types
  • k = 2 machines
  • composition = [[1, 1], [1, 2]]
    • Machine 0 needs: 1 unit of metal 0 and 1 unit of metal 1 per alloy
    • Machine 1 needs: 1 unit of metal 0 and 2 units of metal 1 per alloy
  • stock = [1, 1] (we have 1 unit of each metal type)
  • cost = [2, 3] (metal 0 costs 2 coins/unit, metal 1 costs 3 coins/unit)
  • budget = 10 coins

Step 1: Try Machine 0 (composition [1, 1])

Binary search for maximum alloys:

  • Initial bounds: l = 0, r = 10 + 1 = 11

Iteration 1:

  • mid = (0 + 11 + 1) >> 1 = 6
  • To make 6 alloys: need 6 units of metal 0, 6 units of metal 1
  • Cost calculation:
    • Metal 0: max(0, 6 - 1) * 2 = 5 * 2 = 10 coins
    • Metal 1: max(0, 6 - 1) * 3 = 5 * 3 = 15 coins
    • Total: 25 coins > 10 (budget)
  • Too expensive! Set r = 5

Iteration 2:

  • mid = (0 + 5 + 1) >> 1 = 3
  • To make 3 alloys: need 3 units of metal 0, 3 units of metal 1
  • Cost calculation:
    • Metal 0: max(0, 3 - 1) * 2 = 2 * 2 = 4 coins
    • Metal 1: max(0, 3 - 1) * 3 = 2 * 3 = 6 coins
    • Total: 10 coins = 10 (budget)
  • Affordable! Set l = 3

Iteration 3:

  • mid = (3 + 5 + 1) >> 1 = 4
  • To make 4 alloys: need 4 units of metal 0, 4 units of metal 1
  • Cost calculation:
    • Metal 0: max(0, 4 - 1) * 2 = 3 * 2 = 6 coins
    • Metal 1: max(0, 4 - 1) * 3 = 3 * 3 = 9 coins
    • Total: 15 coins > 10 (budget)
  • Too expensive! Set r = 3

Binary search terminates with l = 3. Machine 0 can make maximum 3 alloys.

Step 2: Try Machine 1 (composition [1, 2])

Binary search for maximum alloys:

  • Initial bounds: l = 0, r = 11

Iteration 1:

  • mid = 6
  • To make 6 alloys: need 6 units of metal 0, 12 units of metal 1
  • Cost calculation:
    • Metal 0: max(0, 6 - 1) * 2 = 5 * 2 = 10 coins
    • Metal 1: max(0, 12 - 1) * 3 = 11 * 3 = 33 coins
    • Total: 43 coins > 10 (budget)
  • Too expensive! Set r = 5

Iteration 2:

  • mid = 3
  • To make 3 alloys: need 3 units of metal 0, 6 units of metal 1
  • Cost calculation:
    • Metal 0: max(0, 3 - 1) * 2 = 2 * 2 = 4 coins
    • Metal 1: max(0, 6 - 1) * 3 = 5 * 3 = 15 coins
    • Total: 19 coins > 10 (budget)
  • Too expensive! Set r = 2

Iteration 3:

  • mid = 1
  • To make 1 alloy: need 1 unit of metal 0, 2 units of metal 1
  • Cost calculation:
    • Metal 0: max(0, 1 - 1) * 2 = 0 * 2 = 0 coins (have enough stock)
    • Metal 1: max(0, 2 - 1) * 3 = 1 * 3 = 3 coins
    • Total: 3 coins ≤ 10 (budget)
  • Affordable! Set l = 1

Iteration 4:

  • mid = 2
  • To make 2 alloys: need 2 units of metal 0, 4 units of metal 1
  • Cost calculation:
    • Metal 0: max(0, 2 - 1) * 2 = 1 * 2 = 2 coins
    • Metal 1: max(0, 4 - 1) * 3 = 3 * 3 = 9 coins
    • Total: 11 coins > 10 (budget)
  • Too expensive! Set r = 1

Binary search terminates with l = 1. Machine 1 can make maximum 1 alloy.

Step 3: Return the maximum

  • Machine 0: 3 alloys
  • Machine 1: 1 alloy
  • Maximum: 3 alloys

The answer is 3, achieved by using Machine 0 to create 3 alloys with exactly the budget of 10 coins.

Time and Space Complexity

Time Complexity: O(k × n × log M), where k is the number of alloy types (machines), n is the number of metal types, and M is the upper bound for binary search. In this problem, M = budget + stock[0] ≤ 2 × 10^8.

  • The outer loop iterates through k different compositions (alloy types)
  • For each composition, binary search is performed with O(log M) iterations
  • In each binary search iteration, we calculate the cost using sum(max(0, mid * x - y) * z for x, y, z in zip(c, stock, cost)), which takes O(n) time to iterate through all n metal types
  • Total: O(k) × O(log M) × O(n) = O(k × n × log M)

Space Complexity: O(1)

  • The algorithm uses only a constant amount of extra space for variables like ans, l, r, mid, and s
  • The generator expression in the sum calculation doesn't create additional lists, it computes values on-the-fly
  • No additional data structures are created that scale with input size

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Wrong Binary Search Template Variant

Pitfall: Using while left < right with right = mid instead of the standard template with while left <= right and right = mid - 1.

Common incorrect pattern:

# WRONG: Non-standard template while left < right:  mid = (left + right + 1) >> 1  if can_produce(mid):  left = mid  else:  right = mid - 1 return left

Solution: Use the standard template with first_true_index:

# CORRECT: Standard template left, right = 0, upper_bound first_true_index = -1  while left <= right:  mid = left + (right - left) // 2  if exceeds_budget(mid): # feasible condition (inverted)  first_true_index = mid  right = mid - 1  else:  left = mid + 1  return first_true_index - 1 if first_true_index != -1 else upper_bound

2. Incorrect Binary Search Upper Bound

Pitfall: Using budget + stock[0] as the upper bound only considers the first metal's stock, which may be insufficient.

Why it's problematic:

  • Different metals have different costs and stock amounts
  • The first metal's stock is arbitrary and may not reflect actual constraints

Solution: Use a sufficiently large upper bound or calculate more carefully:

right = budget + min(stock) # More conservative # Or simply use a large enough value: right = 10**9

3. Integer Overflow in Cost Calculation

Pitfall: When calculating mid * required, this multiplication can overflow for large values.

Example: mid = 10^9, required = 10^5 → Product = 10^14

Solution: Use appropriate data types (long long in C++/Java, Python handles this automatically).

4. Not Handling Edge Cases

Pitfall: Missing edge cases like empty composition arrays or zero budget.

Solution: Add explicit edge case handling:

if not composition or not composition[0]:  return 0
Loading...
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Recommended Readings

Vanilla Binary Search

https assets algo monster cover_photos Binary_Search svg Binary Search Intuition Binary search is an efficient array search algorithm It works by narrowing down the search range by half each time If you have looked up a word in a physical dictionary you've already used binary search in real life Let's

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion If you prefer videos here's a video that explains recursion in a fun and easy way Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask him

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More