# 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

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/binary-search/bs-over-answer-space-answer-space/2861.-maximum-number-of-alloys.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.