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.

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