Problem statement

A foundry works with n kinds of metal and owns k machines. Machine i makes one unit of alloy from composition[i][j] units of metal j, for every j.

The foundry already holds stock[j] units of metal j and can buy more at cost[j] coins per unit, spending at most budget coins in total.

All alloy must be produced on one machine of your choice. Return the maximum number of alloy units the foundry can make.

Example 1

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: On machine 0, five alloys need 5 of metals 0 and 1 (cost 5 + 10) and the stock of metal 2 covers the rest.

Example 2

Input: n = 2, k = 2, budget = 20, composition = [[1,2],[3,1]], stock = [2,1], cost = [2,3]
Output: 3

Example 3

Input: n = 1, k = 1, budget = 0, composition = [[4]], stock = [9], cost = [7]
Output: 2

Constraints

• 1 <= n, k <= 100
• 0 <= budget <= 10^8
• composition.length == k
• composition[i].length == n
• 1 <= composition[i][j] <= 100
• stock.length == cost.length == n
• 0 <= stock[j] <= 10^8
• 1 <= cost[j] <= 100

Hints for Maximum Number of Alloys

1. Hint 1

   Handle each machine on its own and keep the best result.

2. Hint 2

   For one machine, the coins needed to make x alloys grow with x: Σ max(0, x · composition[i][j] - stock[j]) · cost[j].

3. Hint 3

   Binary-search the largest x whose cost fits in the budget; budget + max(stock) is a safe upper bound.

How to solve Maximum Number of Alloys

Since only one machine may be used, solve each machine separately. For a fixed machine, the money required is a non-decreasing function of the number of alloys, so the largest affordable count is found by binary search.

Approach

1. For machine i, define need(x) = Σ_j max(0, x · composition[i][j] - stock[j]) · cost[j], computed in 64-bit and abandoned early once it passes budget.
2. Binary-search x in [0, budget + max(stock)] for the largest value with need(x) <= budget.
3. Return the maximum over all machines.

Why it works

Every term of need is non-decreasing in x, so the set of affordable x is a prefix 0..X and binary search finds X exactly. No machine can make more than stock[j] + budget alloys (each alloy needs at least one unit of metal j, and each extra unit costs at least one coin), which justifies the upper bound.

Complexity

• Time — O(k · n · log(budget + max stock))
• Space — O(1)

Pitfalls

• x · composition[i][j] can reach 2 · 10^10 — compute in 64-bit.
• Do not mix machines: the whole order must come from a single machine.
• A budget of 0 can still allow alloys when the stock suffices.

Reference solution

Python

from typing import List

def maxNumberOfAlloys(n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:
    def affordable(comp, x):
        spent = 0
        for j in range(n):
            lack = x * comp[j] - stock[j]
            if lack > 0:
                spent += lack * cost[j]
                if spent > budget:
                    return False
        return True

    best = 0
    top = budget + max(stock)
    for comp in composition:
        lo, hi = 0, top
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if affordable(comp, mid):
                lo = mid
            else:
                hi = mid - 1
        best = max(best, lo)
    return best

Java

public static int maxNumberOfAlloys(int n, int k, int budget, int[][] composition, int[] stock, int[] cost) {
    int maxStock = 0;
    for (int s : stock) maxStock = Math.max(maxStock, s);
    int best = 0;
    for (int i = 0; i < k; i++) {
        int lo = 0, hi = budget + maxStock;
        while (lo < hi) {
            int mid = lo + (hi - lo + 1) / 2;
            if (alloyAffordable(composition[i], stock, cost, budget, mid)) lo = mid; else hi = mid - 1;
        }
        best = Math.max(best, lo);
    }
    return best;
}

static boolean alloyAffordable(int[] comp, int[] stock, int[] cost, long budget, long x) {
    long spent = 0;
    for (int j = 0; j < comp.length; j++) {
        long lack = x * comp[j] - stock[j];
        if (lack > 0) {
            spent += lack * cost[j];
            if (spent > budget) return false;
        }
    }
    return true;
}

C++

bool alloyAffordable(const vector<int>& comp, const vector<int>& stock, const vector<int>& cost, long long budget, long long x) {
    long long spent = 0;
    for (size_t j = 0; j < comp.size(); j++) {
        long long lack = x * comp[j] - stock[j];
        if (lack > 0) {
            spent += lack * cost[j];
            if (spent > budget) return false;
        }
    }
    return true;
}

int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {
    int maxStock = *max_element(stock.begin(), stock.end());
    int best = 0;
    for (int i = 0; i < k; i++) {
        int lo = 0, hi = budget + maxStock;
        while (lo < hi) {
            int mid = lo + (hi - lo + 1) / 2;
            if (alloyAffordable(composition[i], stock, cost, budget, mid)) lo = mid; else hi = mid - 1;
        }
        best = max(best, lo);
    }
    return best;
}

JavaScript

var maxNumberOfAlloys = function(n, k, budget, composition, stock, cost) {
    var affordable = function(comp, x) {
        var spent = 0;
        for (var j = 0; j < n; j++) {
            var lack = x * comp[j] - stock[j];
            if (lack > 0) {
                spent += lack * cost[j];
                if (spent > budget) return false;
            }
        }
        return true;
    };
    var top = budget;
    var maxStock = 0;
    for (var j = 0; j < n; j++) if (stock[j] > maxStock) maxStock = stock[j];
    top += maxStock;
    var best = 0;
    for (var i = 0; i < k; i++) {
        var lo = 0, hi = top;
        while (lo < hi) {
            var mid = lo + Math.floor((hi - lo + 1) / 2);
            if (affordable(composition[i], mid)) lo = mid; else hi = mid - 1;
        }
        if (lo > best) best = lo;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium