# Maximum Number of Alloys **Difficulty:** MEDIUM [External](https://leetcode.com/problems/maximum-number-of-alloys) Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-alloys **Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search) **Data structures:** Array **Companies:** [MathWorks](https://scaleengineer.com/companies/mathworks) --- ## Problem 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` # Approaches ## Brute Force by Iterating Number of Alloys This approach simulates the process for each machine one by one. For each of the `k` machines, we try to find the maximum number of alloys it can produce. We do this by iteratively checking the cost for producing 1 alloy, 2 alloys, 3 alloys, and so on, until the cost exceeds the given `budget`. The maximum number of alloys found across all machines is the answer. **Time:** O(k * M * n), where `M` is the maximum possible number of alloys. Given the constraints, `M` can be up to `budget + max(stock)`, which is around `2 * 10^8`. This makes the complexity `O(100 * 2*10^8 * 100)`, which is too high for the given time limits. · **Space:** O(1), as we only use a few variables for calculations, not counting the input storage. **Pros:** Simple to understand and implement.; Directly translates the problem statement into code without complex algorithms. **Cons:** Extremely inefficient for the given constraints. The maximum number of alloys can be very large (up to `2 * 10^8`), causing the inner loop to run too many times.; This approach will almost certainly lead to a 'Time Limit Exceeded' (TLE) error on competitive programming platforms. ### Explanation The main idea is to exhaustively check every possibility. Since we must use only one type of machine, we can iterate through each of the `k` machines. For a fixed machine `i`, we need to find the maximum number of alloys, let's call it `x`, that we can create. We can find this `x` by checking `x = 1, 2, 3, ...` sequentially. For each value of `x`, we calculate the total cost. The cost to produce `x` alloys with machine `i` is calculated as follows: - For each metal `j` (from 0 to `n-1`), the total units needed are `x * composition[i][j]`. - We have `stock[j]` units available. - The units of metal `j` to purchase are `max(0, (long)x * composition[i][j] - stock[j])`. - The cost for metal `j` is `(units to purchase) * cost[j]`. - The total cost is the sum of costs for all `n` metals. Note that intermediate calculations can exceed 32-bit integer limits, so using 64-bit integers (`long`) is necessary. We continue incrementing `x` as long as the total cost is within the `budget`. The last value of `x` for which the cost was within budget is the maximum for machine `i`. We repeat this for all `k` machines and keep track of the overall maximum number of alloys possible. ```java class Solution { public int maxNumberOfAlloys(int n, int k, int budget, List> composition, List stock, List cost) { int maxAlloys = 0; for (int i = 0; i < k; i++) { int numAlloys = 0; while (true) { long alloysToTest = numAlloys + 1; long currentCost = 0; for (int j = 0; j < n; j++) { long required = alloysToTest * composition.get(i).get(j); if (required > stock.get(j)) { currentCost += (required - stock.get(j)) * cost.get(j); } if (currentCost > budget) { break; } } if (currentCost <= budget) { numAlloys++; } else { break; // Cannot afford alloysToTest, so numAlloys is the max for this machine } } maxAlloys = Math.max(maxAlloys, numAlloys); } return maxAlloys; } } ``` ### Algorithm - Initialize a variable `max_alloys` to 0. - Loop through each machine `i` from 0 to `k-1`. - Initialize `num_alloys_for_machine_i = 0`. - Start a loop, checking the number of alloys `x = 1, 2, 3, ...`. - For each `x`, calculate the cost to produce `x` alloys using machine `i`. - The cost is calculated as `cost(x) = sum(max(0, x * composition[i][j] - stock[j]) * cost[j])` for all metals `j` from `0` to `n-1`. - If `cost(x)` is less than or equal to the `budget`, it means we can afford to make `x` alloys. We update `num_alloys_for_machine_i = x` and proceed to check `x+1`. - If `cost(x)` exceeds the `budget`, we cannot afford `x` alloys, and since the cost is always increasing, we cannot afford any number greater than `x` either. We break the inner loop. - After the inner loop, update `max_alloys = max(max_alloys, num_alloys_for_machine_i)`. - After checking all `k` machines, return `max_alloys`. ## Binary Search for Number of Alloys This approach improves upon the brute-force method by recognizing a key property: the cost to produce alloys is a monotonically increasing function of the number of alloys. If we can afford to make `x` alloys, we can also afford any number of alloys less than `x`. This property allows us to use binary search to efficiently find the maximum number of alloys for each machine. **Time:** O(k * n * log(M)), where `M` is the size of the search space for the number of alloys (e.g., `2 * 10^8`). With the given constraints, this is approximately `100 * 100 * log(2*10^8)`, which is very efficient. · **Space:** O(1), aside from the input storage. The binary search is done in-place and does not require additional data structures proportional to the input size. **Pros:** Highly efficient due to the logarithmic time complexity of the search for each machine.; Guaranteed to find the optimal solution within the time limits for the given constraints. **Cons:** Slightly more complex to conceptualize and implement than the brute-force approach.; Requires careful handling of potential integer overflows by using 64-bit integers (`long`) for cost calculations. ### Explanation The overall structure is to iterate through each of the `k` machines, find the maximum alloys possible with that machine, and then take the overall maximum. The key improvement is using binary search to find the maximum alloys for a single machine. For a given machine `i`, we want to find the maximum `x` such that `cost(x) <= budget`. Since `cost(x)` is monotonic, we can binary search for `x`. We define a search space for `x`. The lower bound is `0`. The upper bound can be estimated. The number of alloys is limited by the budget and stock. A safe upper bound is `budget + max(stock)`, which is roughly `2 * 10^8`. We can use a slightly larger constant like `200000007`. The binary search for a machine `i` works as follows: 1. Set `low = 0`, `high = 200000007`, `ans = 0`. 2. While `low <= high`: a. Calculate `mid = low + (high - low) / 2`. b. Check if it's possible to create `mid` alloys within the budget using a helper function `canCreate(mid)`. c. The `canCreate(mid)` function calculates the cost for `mid` alloys: `cost(mid) = sum(max(0, mid * composition[i][j] - stock[j]) * cost[j])`. d. If `cost(mid) <= budget`, it means `mid` is a possible number of alloys. We might be able to do even better, so we store `mid` as a potential answer and search in the upper half: `ans = mid`, `low = mid + 1`. e. If `cost(mid) > budget`, `mid` is too many alloys. We must try a smaller number. We search in the lower half: `high = mid - 1`. After the binary search loop finishes, `ans` will hold the maximum number of alloys for machine `i`. We do this for all `k` machines and return the maximum `ans` found. ```java class Solution { public int maxNumberOfAlloys(int n, int k, int budget, List> composition, List stock, List cost) { int maxAlloys = 0; for (int i = 0; i < k; i++) { // Binary search for the max alloys for machine i int low = 0; // A safe upper bound. Max budget is 10^8, min cost is 1, min composition is 1. // If we have 0 stock, we can make at most budget alloys. // If we have max stock 10^8, we can make 10^8 alloys for free. // So, a safe upper bound is budget + max_stock, roughly 2*10^8. int high = 200000007; int ansForMachine = 0; while (low <= high) { int mid = low + (high - low) / 2; if (canCreate(mid, i, n, budget, composition, stock, cost)) { ansForMachine = mid; low = mid + 1; // Try for more } else { high = mid - 1; // Too expensive, try for less } } maxAlloys = Math.max(maxAlloys, ansForMachine); } return maxAlloys; } private boolean canCreate(long numAlloys, int machineIndex, int n, long budget, List> composition, List stock, List cost) { if (numAlloys == 0) return true; long totalCost = 0; List machineComp = composition.get(machineIndex); for (int j = 0; j < n; j++) { long requiredMetal = numAlloys * machineComp.get(j); long stockMetal = stock.get(j); if (requiredMetal > stockMetal) { long metalToBuy = requiredMetal - stockMetal; totalCost += metalToBuy * cost.get(j); } if (totalCost > budget) { return false; } } return true; } } ``` ### Algorithm - Initialize `max_alloys = 0`. - For each machine `i` from `0` to `k-1`: - Perform a binary search to find the maximum number of alloys `x_i` this machine can produce. - Set a search range `low = 0`, `high = 2 * 10^8 + 7` (a safe upper bound). - Initialize `ans_i = 0`. - While `low <= high`: - `mid = low + (high - low) / 2`. - Check if it's possible to create `mid` alloys. This check involves calculating the total cost for `mid` alloys and comparing it with the `budget`. - If it is possible (cost <= budget): `mid` is a potential answer. Store it (`ans_i = mid`) and try for more by searching in the upper half (`low = mid + 1`). - If it is not possible (cost > budget): `mid` is too many. Try for fewer by searching in the lower half (`high = mid - 1`). - After the binary search, update `max_alloys = max(max_alloys, ans_i)`. - Return `max_alloys`. # Solutions ### Java ```java class Solution { int n; int budget; List> composition; List stock; List cost; boolean isValid(long target) { for (List currMachine : composition) { long remain = budget; for (int j = 0; j < n && remain >= 0; j++) { long need = Math.max(0, currMachine.get(j) * target - stock.get(j)); remain -= need * cost.get(j); } if (remain >= 0) { return true; } } return false; } public int maxNumberOfAlloys(int n, int k, int budget, List> composition, List stock, List cost) { this.n = n; this.budget = budget; this.composition = composition; this.stock = stock; this.cost = cost; int l = -1; int r = budget / cost.get(0) + stock.get(0); while (l < r) { int mid = (l + r + 1) >> 1; if (isValid(mid)) { l = mid; } else { r = mid - 1; } } return l; } } ``` ### CPP ```cpp class Solution { public: int maxNumberOfAlloys(int n, int k, int budget, vector> &composition, vector &stock, vector &cost) { auto isValid = [&](long long target) { for (int i = 0; i < k; i++) { long long remain = budget; auto currMachine = composition[i]; for (int j = 0; j < n && remain >= 0; j++) { long long need = max(0LL, target * currMachine[j] - stock[j]); remain -= need * cost[j]; } if (remain >= 0) { return true; } } return false; }; long long l = 0, r = budget + stock[0]; while (l < r) { long long mid = (l + r + 1) >> 1; if (isValid(mid)) { l = mid; } else { r = mid - 1; } } return l; } }; ``` ### Python ```python 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 ```