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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

1
2
3
4
5
6
7
8
9

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

1
2
3
4
5
6
7
8

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 <= 10^8
  • composition.length == k
  • composition[i].length == n
  • 1 <= composition[i][j] <= 100
  • stock.length == cost.length == n
  • 0 <= stock[i] <= 10^8
  • 1 <= cost[i] <= 100

Solution

Method 1 – Binary Search + Greedy

Intuition

We want to maximize the number of alloys we can make using one machine, given limited stock and a budget for buying more metals. For any fixed number of alloys, we can check if it’s possible to make that many alloys with any machine within the budget. We use binary search to find the maximum possible number.

Approach

  1. Use binary search on the answer: the number of alloys (low = 0, high = 10^8).
  2. For each mid value, check if it’s possible to make mid alloys with any machine:
    • For each machine, calculate the total cost to make mid alloys:
      • For each metal type, compute how much more is needed beyond stock and multiply by cost.
      • Sum up the costs for all metals.
    • If any machine can make mid alloys within the budget, it’s possible.
  3. Adjust binary search bounds based on feasibility.
  4. Return the maximum number found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {
        int l = 0, r = 1e8, ans = 0;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            bool ok = false;
            for (int i = 0; i < k; ++i) {
                long long total = 0;
                for (int j = 0; j < n; ++j) {
                    long long need = 1LL * composition[i][j] * mid - stock[j];
                    if (need > 0) total += need * cost[j];
                }
                if (total <= budget) ok = true;
            }
            if (ok) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

func maxNumberOfAlloys(n, k, budget int, composition [][]int, stock, cost []int) int {
    l, r, ans := 0, 1e8, 0
    for l <= r {
        mid := (l + r) / 2
        ok := false
        for i := 0; i < k; i++ {
            total := 0
            for j := 0; j < n; j++ {
                need := composition[i][j]*mid - stock[j]
                if need > 0 {
                    total += need * cost[j]
                }
            }
            if total <= budget {
                ok = true
            }
        }
        if ok {
            ans = mid
            l = mid + 1
        } else {
            r = mid - 1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public int maxNumberOfAlloys(int n, int k, int budget, int[][] composition, int[] stock, int[] cost) {
        int l = 0, r = (int)1e8, ans = 0;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            boolean ok = false;
            for (int i = 0; i < k; i++) {
                long total = 0;
                for (int j = 0; j < n; j++) {
                    long need = 1L * composition[i][j] * mid - stock[j];
                    if (need > 0) total += need * cost[j];
                }
                if (total <= budget) ok = true;
            }
            if (ok) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    fun maxNumberOfAlloys(n: Int, k: Int, budget: Int, composition: Array<IntArray>, stock: IntArray, cost: IntArray): Int {
        var l = 0
        var r = 1e8.toInt()
        var ans = 0
        while (l <= r) {
            val mid = (l + r) / 2
            var ok = false
            for (i in 0 until k) {
                var total = 0L
                for (j in 0 until n) {
                    val need = 1L * composition[i][j] * mid - stock[j]
                    if (need > 0) total += need * cost[j]
                }
                if (total <= budget) ok = true
            }
            if (ok) {
                ans = mid
                l = mid + 1
            } else {
                r = mid - 1
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: list[list[int]], stock: list[int], cost: list[int]) -> int:
        l, r, ans = 0, 10**8, 0
        while l <= r:
            mid = (l + r) // 2
            ok = False
            for i in range(k):
                total = 0
                for j in range(n):
                    need = composition[i][j] * mid - stock[j]
                    if need > 0:
                        total += need * cost[j]
                if total <= budget:
                    ok = True
            if ok:
                ans = mid
                l = mid + 1
            else:
                r = mid - 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

impl Solution {
    pub fn max_number_of_alloys(n: i32, k: i32, budget: i32, composition: Vec<Vec<i32>>, stock: Vec<i32>, cost: Vec<i32>) -> i32 {
        let (n, k) = (n as usize, k as usize);
        let mut l = 0;
        let mut r = 100_000_000;
        let mut ans = 0;
        while l <= r {
            let mid = (l + r) / 2;
            let mut ok = false;
            for i in 0..k {
                let mut total = 0i64;
                for j in 0..n {
                    let need = composition[i][j] as i64 * mid as i64 - stock[j] as i64;
                    if need > 0 {
                        total += need * cost[j] as i64;
                    }
                }
                if total <= budget as i64 {
                    ok = true;
                }
            }
            if ok {
                ans = mid;
                l = mid + 1;
            } else {
                if mid == 0 { break; }
                r = mid - 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    maxNumberOfAlloys(n: number, k: number, budget: number, composition: number[][], stock: number[], cost: number[]): number {
        let l = 0, r = 1e8, ans = 0;
        while (l <= r) {
            const mid = Math.floor((l + r) / 2);
            let ok = false;
            for (let i = 0; i < k; i++) {
                let total = 0;
                for (let j = 0; j < n; j++) {
                    const need = composition[i][j] * mid - stock[j];
                    if (need > 0) total += need * cost[j];
                }
                if (total <= budget) ok = true;
            }
            if (ok) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(k * n * log(maxAlloys)), where maxAlloys is up to 10^8. For each binary search step, we check all machines and all metals.
  • 🧺 Space complexity: O(1) (ignoring input), as we use only a few variables for computation.