Maximum number of alloys

Array Binary Search

40.3% acceptance

Feb 25, 2026

302

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 the company can create.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

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 = n as usize;
    let k = k as usize;
    let budget = budget as i64;
    // Binary search on answer for each machine
    let can_make = |machine: usize, amount: i64| -> bool {
      let mut spend = 0i64;
      for j in 0..n {
        let need = composition[machine][j] as i64 * amount;
        let have = stock[j] as i64;
        if need > have {
          spend += (need - have) * cost[j] as i64;
          if spend > budget { return false; }
        }
      }
      spend <= budget
    };
    let mut ans = 0i32;
    for m in 0..k {
      let mut lo = 0i64;
      let mut hi = 1_000_000_000i64;
      while lo < hi {
        let mid = (lo + hi + 1) / 2;
        if can_make(m, mid) { lo = mid; } else { hi = mid - 1; }
      }
      ans = ans.max(lo as i32);
    }
    ans
  }
}