Skip to content

3155. Maximum Number of Upgradable Servers

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  vector<int> maxUpgrades(vector<int>& count, vector<int>& upgrade,
                          vector<int>& sell, vector<int>& money) {
    // If there's enough money, upgrade all servers; otherwise, optimize by
    // upgrading x servers. We have x * upgrade <= money + (count - x) * sell.
    // Therefore, x = (money + count * sell) / (sell + upgrade).
    vector<int> ans;
    for (int i = 0; i < count.size(); ++i)
      ans.push_back(min(
          count[i],
          static_cast<int>((money[i] + static_cast<long>(count[i]) * sell[i]) /
                           (sell[i] + upgrade[i]))));
    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
  public int[] maxUpgrades(int[] count, int[] upgrade, int[] sell, int[] money) {
    // If there's enough money, upgrade all servers; otherwise, optimize by
    // upgrading x servers. We have x * upgrade <= money + (count - x) * sell.
    // Therefore, x = (money + count * sell) / (sell + upgrade).
    int[] ans = new int[count.length];
    for (int i = 0; i < count.length; ++i)
      ans[i] = Math.min(count[i], //
                        (int) ((money[i] + 1L * count[i] * sell[i]) / (sell[i] + upgrade[i])));
    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def maxUpgrades(
      self,
      count: list[int],
      upgrade: list[int],
      sell: list[int],
      money: list[int],
  ) -> list[int]:
    # If there's enough money, upgrade all servers; otherwise, optimize by
    # upgrading x servers. We have x * upgrade <= money + (count - x) * sell.
    # Therefore, x = (money + count * sell) / (sell + upgrade).
    return [min(c, (m + c * s) // (s + u))
            for c, u, s, m in zip(count, upgrade, sell, money)]