Welcome to Subscribe On Youtube
3155. Maximum Number of Upgradable Servers ðŸ”’
Description
You have n
data centers and need to upgrade their servers.
You are given four arrays count
, upgrade
, sell
, and money
of length n
, which show:
 The number of servers
 The cost of upgrading a single server
 The money you get by selling a server
 The money you initially have
for each data center respectively.
Return an array answer
, where for each data center, the corresponding element in answer
represents the maximum number of servers that can be upgraded.
Note that the money from one data center cannot be used for another data center.
Example 1:
Input: count = [4,3], upgrade = [3,5], sell = [4,2], money = [8,9]
Output: [3,2]
Explanation:
For the first data center, if we sell one server, we'll have 8 + 4 = 12
units of money and we can upgrade the remaining 3 servers.
For the second data center, if we sell one server, we'll have 9 + 2 = 11
units of money and we can upgrade the remaining 2 servers.
Example 2:
Input: count = [1], upgrade = [2], sell = [1], money = [1]
Output: [0]
Constraints:
1 <= count.length == upgrade.length == sell.length == money.length <= 10^{5}
1 <= count[i], upgrade[i], sell[i], money[i] <= 10^{5}
Solutions
Solution 1: Mathematics
For each data center, we assume that we can upgrade $x$ servers, then $x \times \text{upgrade[i]} \leq \text{count[i]} \times \text{sell[i]} + \text{money[i]}$. That is, $x \leq \frac{\text{count[i]} \times \text{sell[i]} + \text{money[i]}}{\text{upgrade[i]} + \text{sell[i]}}$. Also, $x \leq \text{count[i]}$, so we can take the minimum of the two.
The time complexity is $O(n)$, where $n$ is the length of the array. Ignoring the space consumption of the answer array, the space complexity is $O(1)$.

class Solution { public int[] maxUpgrades(int[] count, int[] upgrade, int[] sell, int[] money) { int n = count.length; int[] ans = new int[n]; for (int i = 0; i < n; ++i) { ans[i] = Math.min( count[i], (int) ((1L * count[i] * sell[i] + money[i]) / (upgrade[i] + sell[i]))); } return ans; } }

class Solution { public: vector<int> maxUpgrades(vector<int>& count, vector<int>& upgrade, vector<int>& sell, vector<int>& money) { int n = count.size(); vector<int> ans; for (int i = 0; i < n; ++i) { ans.push_back(min(count[i], (int) ((1LL * count[i] * sell[i] + money[i]) / (upgrade[i] + sell[i])))); } return ans; } };

class Solution: def maxUpgrades( self, count: List[int], upgrade: List[int], sell: List[int], money: List[int] ) > List[int]: ans = [] for cnt, cost, income, cash in zip(count, upgrade, sell, money): ans.append(min(cnt, (cnt * income + cash) // (cost + income))) return ans

func maxUpgrades(count []int, upgrade []int, sell []int, money []int) (ans []int) { for i, cnt := range count { ans = append(ans, min(cnt, (cnt*sell[i]+money[i])/(upgrade[i]+sell[i]))) } return }

function maxUpgrades( count: number[], upgrade: number[], sell: number[], money: number[], ): number[] { const n = count.length; const ans: number[] = []; for (let i = 0; i < n; ++i) { const x = ((count[i] * sell[i] + money[i]) / (upgrade[i] + sell[i]))  0; ans.push(Math.min(x, count[i])); } return ans; }