Maximum Number of Alloys

Maximum Number of Alloys

What is this problem about?

The Maximum Number of Alloys coding problem gives you k machines, each capable of producing alloys using n metals in different compositions. You have an initial stock of each metal and a budget to buy additional metal. Given the cost of each metal and a budget, find the maximum number of alloys you can produce using exactly one machine (the machine you choose to use for all production). The problem requires binary searching on the answer.

Why is this asked in interviews?

Microsoft and MathWorks use this problem to test binary search on the answer — a powerful technique for optimization problems where you can efficiently check feasibility. Candidates who recognize "maximize X subject to budget constraint" as a binary search candidate, and implement the feasibility check correctly across multiple machines, demonstrate strong algorithmic thinking.

Algorithmic pattern used

Binary search on the answer + greedy feasibility check: Binary search on the number of alloys t produced. For a given t and machine k, check if you can produce t alloys within budget: for each metal i, you need composition[k][i] * t units total; you have stock[i] already; the deficit is max(0, composition[k][i]*t - stock[i]); total cost is sum(deficit * cost[i]). If total cost ≤ budget, t is feasible for machine k. Binary search finds the maximum t where at least one machine can feasibly produce t alloys.

Time: O(k * n * log(max_answer)) where max_answer is bounded by the minimum stock + budget/cost.

Example explanation

k=1 machine, n=2 metals. Composition: [[1, 1]]. Stock: [0, 0]. Budget: 3. Costs: [2, 1].

• To produce t alloys: need t metal 0 (cost 2 each) + t metal 1 (cost 1 each) = 3t total.
• t=1: cost=3 ≤ 3. Feasible.
• t=2: cost=6 > 3. Not feasible.
• Answer = 1.

With stock: [1, 0]. Budget: 3. Costs: [2, 1].

• t=1: need 1,1. Have 1,0. Buy: 0 metal 0, 1 metal 1 → cost=1. Feasible.
• t=2: need 2,2. Have 1,0. Buy: 1 metal 0 (cost=2), 2 metal 1 (cost=2) → cost=4 > 3. Not feasible.
• Answer = 1. Wait, with budget=3 and t=1 costing 1, can we try t=2 again? Yes: 12 + 21 = 4 > 3. Not feasible. Answer = 1.

Common mistakes candidates make

• Not iterating over all machines: The answer requires finding the best machine; checking only machine 0 gives wrong results.
• Integer overflow in feasibility check: composition * t * cost can be large. Use 64-bit integers or clamp to budget+1 early.
• Binary search bounds: Lower bound is 0 (produce nothing), upper bound should be derived from maximum possible production given unlimited metal at minimum cost.

Interview preparation tip

For the Array Binary Search interview pattern, "maximize X subject to resource constraint" is a classic binary search on answer template. The feasibility function must be monotone: if you can produce t alloys, you can produce any t' < t. Practice identifying this monotonicity before binary searching, as it's the prerequisite for the technique to be valid.