Leetcode # 2861. Maximum Number of Alloys

Problem

https://leetcode.com/contest/weekly-contest-363/problems/maximum-number-of-alloys/

Solution: Binary Search

Time Complexity: O(max((stock[m] + budget // cost[m]) // machine[m] for m in range(n)) * n)
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:
    
    def is_enough(machine, alloy_n):
      _budget = budget
      for m in range(n):
        _budget -= max(0, (machine[m] * alloy_n - stock[m])) * cost[m]
      return _budget >= 0
    
    result = 0
    for machine in composition:
      left, right = 0, max((stock[m] + budget // cost[m]) // machine[m] for m in range(n)) + 1
      while left < right:
        mid = (left + right) // 2
        if not is_enough(machine, mid):
          right = mid
        else:
          left  = mid + 1
      result = max(result, left - 1)
    return result

Last Updated on 2023/09/19 by A1go