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:
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 <= 1051 <= count[i], upgrade[i], sell[i], money[i] <= 105Problem Overview: You are given an array describing servers and the resources required to upgrade them. Each upgrade consumes a limited shared budget. The task is to determine the maximum number of servers you can upgrade without exceeding the available resources.
Approach 1: Brute Force Simulation (O(n^2) time, O(1) space)
The most direct way is to try upgrading every possible subset size of servers. For a candidate count k, iterate through servers and calculate the resource required to upgrade each one, then check if the total cost of any k servers fits within the budget. This requires repeatedly recomputing upgrade costs and scanning the array. The approach is straightforward but inefficient because each candidate size requires scanning the array and recomputing totals.
Approach 2: Mathematical Cost Calculation + Binary Search (O(n log n) time, O(1) space)
A more efficient solution treats the answer as a monotonic search problem. If you can upgrade k servers within the budget, you can also upgrade any number smaller than k. That property allows binary search over the number of servers. For a given candidate k, compute the minimum cost required to upgrade k servers using a direct mathematical formula derived from the upgrade rules. The calculation iterates through the array and accumulates the resource requirement for each server. If the total exceeds the budget, the candidate is infeasible.
The key insight is that the upgrade requirement can be computed with simple arithmetic rather than simulating each upgrade step. Using mathematical reasoning, you derive the number of operations or resources required per server and sum them efficiently. Binary search reduces the number of checks from n to log n, giving a significant speed improvement.
Recommended for interviews: The mathematical approach with binary search is the expected solution. Brute force demonstrates the basic understanding of the problem constraints, but interviewers look for recognizing the monotonic property and applying binary search to minimize checks while computing upgrade cost using a direct formula.
For each data center, we assume that we can upgrade x servers, then x times upgrade[i] leq count[i] times sell[i] + money[i]. That is, x leq \frac{count[i] times sell[i] + money[i]}{upgrade[i] + sell[i]}. Also, x leq 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).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n^2) | O(1) | Useful for understanding the upgrade cost calculation and validating logic on small inputs |
| Mathematics + Binary Search | O(n log n) | O(1) | Best general solution when the feasibility of upgrading k servers is monotonic |
3155. Maximum Number of Upgradable Servers (Leetcode Medium) • Programming Live with Larry • 525 views views
Practice Maximum Number of Upgradable Servers with our built-in code editor and test cases.
Practice on FleetCode