2861. Maximum Number of Alloys


Problem Description

In this problem, you run a company that specializes in creating alloys from various metals using machines. You have a selection of n different metal types and k machines to use for manufacturing alloys. Each machine has a specific recipe, meaning it requires certain amounts of each metal type to produce one batch of alloy. These recipes are represented by a 2D array composition, where composition[i][j] is the number of units of metal type j required by machine i to create an alloy.

You start with a finite stock of metal units, indicated by a 1-indexed array stock, where stock[i] represents how many units of metal type i you currently have. If you need more of any metal, you can buy additional units, where the cost to purchase one unit of metal type i is cost[i] coins.

Your objective is to maximize the number of alloys you can produce using any one machine, without exceeding your budget of coins. Importantly, all produced alloys must come from the same machine. You're tasked to determine the maximum number of alloys that can be created given your initial resources and financial constraints.

Intuition

To solve this problem, we need to determine, for each machine, how many batches of alloy we can produce given our stock of metals, the ability to buy more metals, and our budget. We repeat this calculation for every machine and then choose the maximum value across all machines.

The intuition behind the solution is to utilize binary search to efficiently find the maximum number of alloys we can produce per machine without surpassing the budget. This is because, for a given machine, if we can produce x alloys, we can certainly produce any number of alloys less than x. Conversely, if we cannot afford to produce x alloys, we cannot afford any number greater than x either. This creates a perfect scenario for using binary search, which is a method for finding an item in a sorted series with an "ordered" relationship by repeatedly halving the search space.

For each machine, we have the following steps:

  1. Initialize the search space for the number of alloys (l as the low end and r as the high end), which is determined by the budget and the existing stock of the first metal type.
  2. Perform binary search to find the maximum number of alloys:
    • Calculate the midpoint mid between the current low l and high r values.
    • Compute the cost needed to produce mid alloys using the current machine, considering our stock and the prices for additional metals.
    • Check if we can afford this cost with our budget:
      • If yes, we update the low end of our search (l) to mid, as we might be able to produce even more alloys.
      • If no, we update the high end of our search (r) to mid - 1, as we cannot afford mid alloys and need to try a smaller number.
    • Repeat this process until l and r converge to the highest affordable number of alloys for this machine.
  3. Keep track of the maximum number of alloys found across all machines.
  4. Return the maximum as the final answer.

Learn more about Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which of the following array represent a max heap?

Solution Approach

The implementation of the solution can be broken down into multiple parts, each aligned with the binary search algorithm used to find the maximum number of alloys that can be produced by a single machine within the budget.

  1. Outer Loop - Iterate Over Each Machine: The solution begins with an outer loop for c in composition: that iterates over each machine's alloy composition. The variable c refers to a specific machine's requirement of metal types from the 2D array composition.

  2. Binary Search Initialization: For each machine, we initialize the binary search range with l, r = 0, budget + stock[0]. This range is a logical start because the number of alloys that can be possibly created is between 0 and some upper limit proportional to the budget and the initial stock.

  3. Binary Search Loop: Within this loop, the algorithm uses binary search to find the optimal number of alloys that can be created with the current machine. The loop while l < r: continues reducing the search space until it converges on the maximum number of alloys.

  4. Midpoint and Cost Calculation:

    • The midpoint mid is calculated using (l + r + 1) >> 1, which is equivalent to (l + r + 1) / 2 but faster as it employs bit shifting.
    • The cost required to create mid alloys is computed with s = sum(max(0, mid * x - y) * z for x, y, z in zip(c, stock, cost)), which calculates the costs taking into consideration the stock already available and the additional purchases required for the shortfall.
  5. Affordability Check:

    • If the calculated cost s is within the budget (if s <= budget:), the algorithm updates the lower bound of the search space l = mid because it is still possible to create mid alloys or potentially more.
    • If the cost s exceeds the budget (else:), the algorithm adjusts the upper bound r = mid - 1 since mid is too high of a number of alloys to afford.
  6. Finding the Maximum:

    • After the binary search converges for a machine, we determine the maximum number of alloys that can be created by this machine without exceeding the budget, which will be the value of l.
    • Then, we update the overall answer ans = max(ans, l), which keeps track of the maximum number of alloys across all machines.
  7. Returning Result: After the loop has processed all machines, return ans yields the final result, which is the maximum number of alloys that can be produced by any one machine within the budget.

This algorithm leverages the binary search pattern due to the sorted nature of the problem space — there's a clear ordering in the problem setup that if x number of alloys can be produced, then any number less than x can also be produced (and vice versa). The binary search pattern effectively narrows down the possibilities, leading to an efficient solution.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement priority queue?

Example Walkthrough

Let's walk through a small example to illustrate how the solution approach would be applied. Imagine we have the following input:

  • Metal types: n = 2 (two types of metal)
  • Machines: k = 1 (one machine)
  • Composition for the machine: composition = [[3, 2]] (requires 3 units of metal type 1 and 2 units of metal type 2 for one batch)
  • Initial stock: stock = [5, 4] (5 units of metal 1 and 4 units of metal 2)
  • Costs to purchase metals: cost = [2, 1] (2 coins per unit of metal 1, 1 coin per unit of metal 2)
  • Budget: budget = 10 coins

We want to calculate the maximum number of alloys we can produce using this machine without exceeding our budget.

Outer Loop - Iterate Over Each Machine

We only have one machine, so our loop will run a single iteration. For our machine, the composition is c = [3, 2].

Binary Search Initialization

We initialize our binary search range with l, r = 0, budget + stock[0]. Since the budget is 10 and we have 5 units of metal 1, our range is l, r = 0, 15.

Binary Search Loop

We now enter the binary search loop:

  1. First Iteration:

    • Calculate midpoint mid = (l + r + 1) >> 1 which is (0 + 15 + 1) >> 1 = 8.
    • Calculate cost s: we would need 8 * 3 = 24 units of metal 1 and 8 * 2 = 16 units of metal 2. We have 5 and 4 units respectively, so we need to purchase 19 more units of metal 1 and 12 units of metal 2, totaling a cost of 19 * 2 + 12 * 1 = 38 + 12 = 50 coins.
    • Since 50 coins exceeds our budget of 10 coins, we set r = mid - 1, so r = 7.
  2. Second Iteration:

    • Midpoint mid = (l + r + 1) >> 1 which is (0 + 7 + 1) >> 1 = 4.
    • Calculate cost s: we would need 4 * 3 = 12 units of metal 1 and 4 * 2 = 8 units of metal 2. This would require buying 7 units of metal 1 and 4 units of metal 2 for 7 * 2 + 4 * 1 = 14 + 4 = 18 coins.
    • Since 18 coins still exceed our budget, we update r = mid - 1, so r = 3.
  3. Third Iteration:

    • Midpoint mid = (l + r + 1) >> 1 which is (0 + 3 + 1) >> 1 = 2.
    • Calculate cost s: Total units needed are 2 * 3 = 6 for metal 1 and 2 * 2 = 4 for metal 2. We need to buy 1 additional unit of metal 1 and no additional units of metal 2, totaling a cost of 1 * 2 + 0 * 1 = 2 coins.
    • This is affordable, so we can update l = mid, which will be l = 2.

The lower and upper bounds of our search l and r have now converged, indicating that with our budget of 10 coins, we can afford to produce up to 2 batches of alloys with the given machine and available stock.

Maximum Number of Alloys

Since we only have a single machine in this example, the maximum number of alloys is the same as what we've determined for the machine: 2 batches.

The number of alloys we can produce by this one machine within our budget of 10 coins is 2, which would be the final output of the algorithm for this example.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxNumberOfAlloys(
5        self,
6        alloys_count: int,
7        elements_count: int,
8        budget: int,
9        composition: List[List[int]],
10        stock: List[int],
11        cost: List[int],
12    ) -> int:
13        # Initialize the maximum number of alloys that can be created to zero.
14        max_alloys = 0
15      
16        # Iterate over each alloy's composition.
17        for comp in composition:
18            # Set the search space for binary search.
19            # We start from zero and go up to the budget plus the available stock for the first element.
20            left, right = 0, budget + stock[0]
21          
22            # Perform binary search to find the maximum amount of alloy that can be produced
23            # within the budget constraints.
24            while left < right:
25                # Check the middle point of the current search space.
26                mid = (left + right + 1) // 2
27              
28                # Calculate the total cost to produce 'mid' units of alloy with the current composition.
29                # If we need more of any element than we have in stock, we buy the extra amount.
30                # The sum accumulates the cost for all elements in the alloy.
31                sum_cost = sum(
32                    max(0, mid * element_comp - current_stock) * element_cost 
33                    for element_comp, current_stock, element_cost in zip(comp, stock, cost)
34                )
35
36                # If the total cost does not exceed the budget, we can afford 'mid' units of this alloy,
37                # so we move the lower bound up to 'mid'.
38                if sum_cost <= budget:
39                    left = mid
40                # Otherwise, it's too expensive, so we bring the upper bound down to 'mid' - 1.
41                else:
42                    right = mid - 1
43          
44            # Update the maximum number of alloys that can be created.
45            max_alloys = max(max_alloys, left)
46      
47        # Return the maximum number of alloys that can be made within the budget for all compositions.
48        return max_alloys
49
1class Solution {
2    int numElements;        // Number of elements to be used
3    int availableBudget;    // Total budget available for purchasing elements
4    List<List<Integer>> alloyComposition; // List containing compositions of each alloy
5    List<Integer> elementStock;  // Stock available for each element
6    List<Integer> elementCost;   // Cost of each element
7
8    // Method to check if it is possible to create 'target' number of alloys within the budget
9    boolean isValid(long target) {
10        // Iterate over each possible alloy composition
11        for (List<Integer> currentMachine : alloyComposition) {
12            long remainingBudget = availableBudget;
13            // Check if the current composition can be made 'target' times within the remaining budget
14            for (int j = 0; j < numElements && remainingBudget >= 0; j++) {
15                long requiredAmount = Math.max(0, currentMachine.get(j) * target - elementStock.get(j));
16                remainingBudget -= requiredAmount * elementCost.get(j);
17            }
18            if (remainingBudget >= 0) {
19                return true; // If we can afford this alloy, return true
20            }
21        }
22        return false; // If none of the compositions fit the budget for 'target' alloys, return false
23    }
24
25    // Method to find the maximum number of alloys that can be produced with the given budget
26    public int maxNumberOfAlloys(int numElements, int k, int availableBudget, List<List<Integer>> alloyComposition,
27                                 List<Integer> elementStock, List<Integer> elementCost) {
28        this.numElements = numElements;
29        this.availableBudget = availableBudget;
30        this.alloyComposition = alloyComposition;
31        this.elementStock = elementStock;
32        this.elementCost = elementCost;
33
34        // Binary search bounds: set initial low to -1 because 0 alloys is always possible
35        int low = -1;
36        // Upper bound of the search space: assume we spend the entire budget on the cheapest element
37        int high = availableBudget / elementCost.get(0) + elementStock.get(0);
38      
39        // Use binary search to find the maximum number of alloys
40        while (low < high) {
41            // Calculate mid-point (use right shift instead of division by 2 for speed)
42            int mid = (low + high + 1) >>> 1;
43            // Check if it's possible to create 'mid' alloys
44            if (isValid(mid)) {
45                low = mid; // If it's valid, shift the lower bound up
46            } else {
47                high = mid - 1; // Otherwise, lower the high bound
48            }
49        }
50        return low; // After binary search, low will hold the maximum number of alloys
51    }
52}
53
1class Solution {
2public:
3    // The function calculates the max number of alloys that can be produced given the constraints
4    int maxNumberOfAlloys(int numElements, int numMachines, int totalBudget, 
5                          vector<vector<int>>& machineComposition, vector<int>& elementStock, 
6                          vector<int>& elementCost) {
7
8        // Helper lambda to check if a given target number of alloys is possible to produce
9        auto isValid = [&](long long target) {
10            // Iterate over all machines to check if any of them can produce the target alloys
11            for (int i = 0; i < numMachines; i++) {
12                long long remainingBudget = totalBudget;
13                auto currentMachine = machineComposition[i];
14                // Iterate over all elements to calculate the cost 
15                for (int j = 0; j < numElements && remainingBudget >= 0; j++) {
16                    // Calculate the additional amount of the element needed
17                    long long neededElementAmount = max(0LL, target * currentMachine[j] - elementStock[j]);
18                    // Deduct the cost from the remaining budget
19                    remainingBudget -= neededElementAmount * elementCost[j];
20                }
21                // If the remaining budget is non-negative, the target is feasible
22                if (remainingBudget >= 0) {
23                    return true;
24                }
25            }
26            // The target is not feasible on any machine
27            return false;
28        };
29
30        // Binary search to find the maximum target possible
31        long long left = 0, right = totalBudget + elementStock[0];
32        while (left < right) {
33            long long mid = (left + right + 1) >> 1; // +1 to avoid infinite loop
34            if (isValid(mid)) {
35                left = mid;  // If valid, narrow the search upwards
36            } else {
37                right = mid - 1;  // If not valid, narrow the search downwards
38            }
39        }
40        // The left pointer will point to the maximum number of alloys that can be produced
41        return left;
42    }
43};
44
1function maxNumberOfAlloys(
2    alloyTypes: number,
3    machines: number,
4    budget: number,
5    compositions: number[][],
6    stocks: number[],
7    costs: number[],
8): number {
9    // Initialize the possible range for the maximum number of alloys
10    let low = 0;
11    let high = budget + stocks[0];
12  
13    // Helper function to check if a target number of alloys can be produced
14    const canProduceTarget = (target: number): boolean => {
15        // Iterate over each machine to check if it can meet the target with the given budget
16        for (const composition of compositions) {
17            let remainingBudget = budget;
18            for (let i = 0; i < alloyTypes; ++i) {
19                // Calculate the amount of material needed beyond the current stock
20                let requiredMaterial = Math.max(0, target * composition[i] - stocks[i]);
21                // Update the remainingBudget by subtracting the cost of required materials
22                remainingBudget -= requiredMaterial * costs[i];
23            }
24            // If at least one machine can produce the target number of alloys, return true
25            if (remainingBudget >= 0) {
26                return true;
27            }
28        }
29        // If no machine can produce the target number of alloys, return false
30        return false;
31    };
32  
33    // Perform binary search to find the maximum number of alloys that can be produced
34    while (low < high) {
35        const mid = (low + high + 1) >> 1;
36        // If the middle point is a valid target, update the lower bound
37        if (canProduceTarget(mid)) {
38            low = mid;
39        } else {
40            // Otherwise, update the upper bound
41            high = mid - 1;
42        }
43    }
44  
45    // Return the maximum number of alloys that can be produced
46    return low;
47}
48
Not Sure What to Study? Take the 2-min Quiz:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Time and Space Complexity

The time complexity of the given code can be analyzed by breaking it down into its fundamental operations. The outer loop iterates over each composition:

1for c in composition:

Since there are n compositions, the outer loop runs n times. Inside this loop, there is a binary search:

1while l < r:
2    mid = (l + r + 1) >> 1
3    s = sum(max(0, mid * x - y) * z for x, y, z in zip(c, stock, cost))
4    if s <= budget:
5        l = mid
6    else:
7        r = mid - 1

Binary search runs in O(log(budget + stock[0])) time because it repeatedly divides the search interval in half until it becomes too small to divide (in this case, the initial range is from 0 to budget + stock[0]). Inside the binary search, there is a sum operation processed in linear time with respect to k, which is the length of the composition, stock, and cost lists.

Combined, the time complexity for the above operation is O(k), because it iterates over the k elements to calculate s. Since the binary search is within a loop over n compositions, we multiply the above to get the total time complexity:

1O(n * k * log(budget + stock[0]))

For space complexity, the code uses a constant amount of extra space, excluding the input data structures. There are no dynamically sized data structures that grow with the size of the input. Therefore, the space complexity is:

1O(1)

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫