#2861

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Maximum Number of Alloys

Determine the maximum number of alloys possible using limited metal stock and budget, leveraging binary search efficiently.

array binary search

Problem Statement

You own a company producing alloys with n types of metals and k machines. Each machine consumes a specific number of units from each metal type per alloy. You start with an initial stock of each metal and can buy additional units at a given cost, constrained by a total budget. Your goal is to maximize the number of alloys that can be created without exceeding the budget.

Each machine i requires composition[i][j] units of metal j for one alloy. Given the arrays stock and cost representing your current inventory and per-unit metal costs, compute the maximum number of alloys possible. Use binary search over the answer space to efficiently determine the solution.

Examples

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

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

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

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

Solution Approach

Binary Search Over Alloys Count

Set left = 0 and right = an upper limit (e.g., budget or max stock ratio). For each mid value, check if creating mid alloys is feasible using current stock and budget. Adjust left or right based on the feasibility check.

Feasibility Check Function

For a candidate alloy count, calculate additional metals needed by subtracting stock from total required for all machines. Multiply by cost to get total expense. If total expense is less than or equal to budget, the candidate is feasible.

Update Search Bounds

If mid alloys are feasible, move left bound to mid + 1 to check higher counts. If not feasible, move right bound to mid - 1. Continue until left exceeds right and return the maximum feasible count.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * k * log(maxAlloys)) where log(maxAlloys) comes from binary search and n * k from computing metal requirements per candidate. Space complexity is O(n) for temporary arrays storing additional metals needed.

What Interviewers Usually Probe

Consider edge cases where stock covers all metal requirements and no purchases are needed.
Be ready to explain why binary search is efficient over iterative simulation of every alloy count.
Discuss how to compute required metals per machine without double counting or overspending the budget.

Common Pitfalls or Variants

Common pitfalls

Miscalculating total required metals for multiple machines leading to incorrect feasibility.
Ignoring the budget limit when stock is insufficient, which may produce invalid answers.
Choosing inappropriate upper bounds for binary search, causing unnecessary iterations or overflow.

Follow-up variants

Restricting machine usage to only once per alloy sequence.
Allowing fractional metal units and computing maximum alloys with floating point division.
Adding dynamic cost changes per unit purchased, requiring updated feasibility computation per iteration.

FAQ

What is the best approach for Maximum Number of Alloys?

Binary search over the possible number of alloys, combined with a feasibility check using stock and cost arrays, efficiently finds the maximum.

How do I handle machines requiring different metal compositions?

Calculate the total metals needed for each candidate alloy count and sum across all machines, then compare against stock and budget.

Why is binary search suitable for this problem?

Because the number of alloys is monotonic: if you can make x alloys, you can make any fewer; if you cannot make x, you cannot make more, enabling efficient search.

How should I set the upper bound for binary search?

Use a large number based on budget divided by minimum metal cost, or sum of stock ratios, ensuring it covers the maximum feasible alloy count.

Can GhostInterview help me debug over-budget calculations?

Yes, it can guide through step-by-step validation of total metal costs against the budget and correct candidate alloy count evaluation.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def maxNumberOfAlloys(
        self,
        n: int,
        k: int,
        budget: int,
        composition: List[List[int]],
        stock: List[int],
        cost: List[int],
    ) -> int:
        ans = 0
        for c in composition:
            l, r = 0, budget + stock[0]
            while l < r:
                mid = (l + r + 1) >> 1
                s = sum(max(0, mid * x - y) * z for x, y, z in zip(c, stock, cost))
                if s <= budget:
                    l = mid
                else:
                    r = mid - 1
            ans = max(ans, l)
        return ans

Continue Practicing

#2856 minimum array length after pair removals #2831 find the longest equal subarray #2830 maximize the profit as the salesman