In this guide, you will get 2861. Maximum Number of Alloys LeetCode Solution with the best time and space complexity. The solution to Maximum Number of Alloys problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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
Complexity Analysis
Time Complexity: O(\log 10^9 \cdot kn)
Space Complexity: O(1)
2861. Maximum Number of Alloys LeetCode Solution in C++
class Solution {
public:
int maxNumberOfAlloys(int n, int k, int budget,
vector<vector<int>>& composition, vector<int>& stock,
vector<int>& cost) {
int l = 1;
int r = 1'000'000'000;
while (l < r) {
const int m = (l + r) / 2;
if (isPossible(n, budget, composition, stock, cost, m))
l = m + 1;
else
r = m;
}
return l - 1;
}
private:
// Returns true if it's possible to create `m` alloys by using any machine.
bool isPossible(int n, int budget, const vector<vector<int>>& composition,
const vector<int>& stock, const vector<int>& costs, int m) {
// Try all the possible machines.
for (const vector<int>& machine : composition) {
long requiredMoney = 0;
for (int j = 0; j < n; ++j) {
const long requiredUnits =
max(0L, static_cast<long>(machine[j]) * m - stock[j]);
requiredMoney += static_cast<long>(requiredUnits) * costs[j];
}
if (requiredMoney <= budget)
return true;
}
return false;
}
}; /* code provided by PROGIEZ */
2861. Maximum Number of Alloys LeetCode Solution in Java
class Solution {
public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition,
List<Integer> stock, List<Integer> cost) {
int l = 1;
int r = 1_000_000_000;
while (l < r) {
final int m = (l + r) / 2;
if (isPossible(n, budget, composition, stock, cost, m))
l = m + 1;
else
r = m;
}
return l - 1;
}
// Returns true if it's possible to create `m` alloys by using any machine.
private boolean isPossible(int n, int budget, List<List<Integer>> composition,
List<Integer> stock, List<Integer> costs, int m) {
// Try all the possible machines.
for (List<Integer> machine : composition) {
long requiredMoney = 0;
for (int j = 0; j < n; ++j) {
final long requiredUnits = Math.max(0L, (long) machine.get(j) * m - stock.get(j));
requiredMoney += requiredUnits * costs.get(j);
}
if (requiredMoney <= budget)
return true;
}
return false;
}
} // code provided by PROGIEZ
2861. Maximum Number of Alloys LeetCode Solution in Python
class Solution:
def maxNumberOfAlloys(self, n: int, k: int, budget: int,
composition: list[list[int]], stock: list[int],
costs: list[int]) -> int:
l = 1
r = 1_000_000_000
def isPossible(m: int) -> bool:
"""Returns True if it's possible to create `m` alloys by using any machine."""
# Try all the possible machines.
for machine in composition:
requiredMoney = 0
for j in range(n):
requiredUnits = max(0, machine[j] * m - stock[j])
requiredMoney += requiredUnits * costs[j]
if requiredMoney <= budget:
return True
return False
while l < r:
m = (l + r) // 2
if isPossible(m):
l = m + 1
else:
r = m
return l - 1 # code by PROGIEZ
