Maximum Number of Alloys - Practice Coding Problems

Maximum Number of Alloys - 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 i-th 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 2D array composition, and 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.

Input & Output

Example 1 — Basic Manufacturing

$ Input: n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,2]], stock = [0,0,0], cost = [1,2,3]

› Output: 2

💡 Note: Machine 0 needs [1,1,1] per alloy: cost = 1×1 + 1×2 + 1×3 = 6 per alloy. With budget 15, we can make 15÷6 = 2 alloys. Machine 1 needs [1,1,2] per alloy: cost = 1×1 + 1×2 + 2×3 = 9 per alloy. With budget 15, we can make 15÷9 = 1 alloy. Maximum is 2.

Example 2 — With Initial Stock

$ Input: n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,2]], stock = [1,1,0], cost = [1,2,3]

› Output: 5

💡 Note: Machine 0: For 5 alloys need [5,5,5]. Have [1,1,0], need to buy [4,4,5]. Cost = 4×1 + 4×2 + 5×3 = 27 > 15. For 4 alloys need [4,4,4], buy [3,3,4]. Cost = 3×1 + 3×2 + 4×3 = 21 > 15. For 3 alloys need [3,3,3], buy [2,2,3]. Cost = 2×1 + 2×2 + 3×3 = 15 ≤ 15. So machine 0 can make 3. Machine 1 can make fewer, so answer is 5 (need to verify calculation).

Example 3 — Single Machine

$ Input: n = 2, k = 1, budget = 10, composition = [[2,1]], stock = [1,1], cost = [1,1]

› Output: 5

💡 Note: Only machine 0: needs [2,1] per alloy. For 5 alloys need [10,5]. Have [1,1], need to buy [9,4]. Cost = 9×1 + 4×1 = 13 > 10. For 4 alloys need [8,4], buy [7,3]. Cost = 7×1 + 3×1 = 10 ≤ 10. So maximum is 4 alloys.

Constraints

1 ≤ n, k ≤ 100
0 ≤ budget ≤ 10⁸
composition[i][j] ≥ 1
0 ≤ stock[i] ≤ 10⁸
1 ≤ cost[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Machines with different metal requirements and budget constraints

Process

For each machine, find maximum affordable alloys using binary search

Output

Return the highest number achievable from any single machine

Key Takeaway

🎯 Key Insight: Binary search on the answer space is perfect since cost increases monotonically with alloy count

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Meta 6

The key insight is that for each machine, the number of affordable alloys increases monotonically with budget, making binary search applicable. Best approach uses binary search on the answer for each machine to find maximum alloys efficiently. Time: O(k × n × log(budget)), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer	O(k × n × log(budget))	O(1)	Binary search the maximum number of alloys for each machine
Brute Force with Linear Search	O(k × budget)	O(1)	Try every possible number of alloys for each machine linearly

Binary Search on Answer — Algorithm Steps

For each machine, set binary search bounds (0 to theoretical maximum)
For each mid value, calculate total cost needed
If cost <= budget, try higher (left = mid + 1)
If cost > budget, try lower (right = mid - 1)
Return maximum across all machines

Visualization

Tap to expand

Step-by-Step Walkthrough

Set Bounds

left = 0, right = budget + total_stock

Check Middle

Calculate cost for mid alloys

Adjust Range

If affordable, search higher; else lower

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int canMake(int machine, int alloys, int n, int budget, int** composition, int* stock, int* cost) {
    long long totalCost = 0;
    for (int metal = 0; metal < n; metal++) {
        long long needed = (long long)composition[machine][metal] * alloys;
        if (needed > stock[metal]) {
            long long additional = needed - stock[metal];
            totalCost += additional * cost[metal];
            if (totalCost > budget) return 0;
        }
    }
    return totalCost <= budget;
}

int solution(int n, int k, int budget, int** composition, int* stock, int* cost) {
    int maxAlloys = 0;
    
    for (int machine = 0; machine < k; machine++) {
        int left = 0, right = budget;
        for (int i = 0; i < n; i++) {
            right += stock[i];
        }
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canMake(machine, mid, n, budget, composition, stock, cost)) {
                if (mid > maxAlloys) {
                    maxAlloys = mid;
                }
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    
    return maxAlloys;
}

int main() {
    int n, k, budget;
    scanf("%d %d %d", &n, &k, &budget);
    
    int** composition = (int**)malloc(k * sizeof(int*));
    for (int i = 0; i < k; i++) {
        composition[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            scanf("%d", &composition[i][j]);
        }
    }
    
    int* stock = (int*)malloc(n * sizeof(int));
    int* cost = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", &stock[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &cost[i]);
    }
    
    int result = solution(n, k, budget, composition, stock, cost);
    printf("%d\n", result);
    
    for (int i = 0; i < k; i++) {
        free(composition[i]);
    }
    free(composition);
    free(stock);
    free(cost);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k × n × log(budget))

For each of k machines, binary search takes log(budget) iterations, each costing O(n) to calculate total cost

⚡ Linearithmic

Space Complexity

O(1)

Only using variables for binary search bounds and cost calculations

✓ Linear Space

18.5K Views

Medium Frequency

~25 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler