# 2861. Maximum Number of Alloys

## Problem Statement

<br>

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*.

&#x20;

**Example 1:**

<pre><code><strong>Input: n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,0], cost = [1,2,3]
</strong><strong>Output: 2
</strong><strong>Explanation: It is optimal to use the 1st machine to create alloys.
</strong>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.
</code></pre>

**Example 2:**

<pre><code><strong>Input: n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,100], cost = [1,2,3]
</strong><strong>Output: 5
</strong><strong>Explanation: It is optimal to use the 2nd machine to create alloys.
</strong>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.
</code></pre>

**Example 3:**

<pre><code><strong>Input: n = 2, k = 3, budget = 10, composition = [[2,1],[1,2],[1,1]], stock = [1,1], cost = [5,5]
</strong><strong>Output: 2
</strong><strong>Explanation: It is optimal to use the 3rd machine to create alloys.
</strong>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.
</code></pre>

&#x20;

**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`

## Intuition

```
Approach:

 To make one alloy using all composition
Hence x = no of alloy
(x*comp[i] - stock[i]) * cost <=budget

Find x using Binary search over search space take 1e12

```

### Links

<https://leetcode.com/problems/maximum-number-of-alloys/description/>

### Video Links

<https://www.youtube.com/watch?v=yOqX3DmEXMQ&ab_channel=AryanMittal>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
typedef long long ll;

class Solution {
public:
    bool is_ok(int n ,int budget, vector<int>& composition, vector<int>& stock, vector<int>& cost, ll mid){
        ll res=0;
        for(int i=0; i<n; i++){
            res += max(mid * composition[i] - stock[i] , 0ll) * cost[i];
        }

        return res<=budget;
    }

    int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {
        ll ans = 0;
        for(auto &it: composition){
            ll low=0, high=1e12, res = 0;

            while(low<=high){
                int mid = low + (high-low)/2;
                if(is_ok(n, budget, it, stock, cost, mid)){
                    res = mid;
                    low = mid+1;
                }
                else
                    high=mid-1;
            }
            ans = max(ans, res);
        }

        return (int)ans;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###