LeetCode 3155 - Maximum Number of Upgradable Servers

The problem requires calculating the maximum number of servers that can be upgraded at each data center independently, given the number of servers, upgrade costs, potential revenue from selling servers, and available money.

leetcodemediumarraymathbinary-search

LeetCode Problem 3155

Difficulty: 🟡 Medium
Topics: Array, Math, Binary Search

Solution

Problem Understanding

The problem requires calculating the maximum number of servers that can be upgraded at each data center independently, given the number of servers, upgrade costs, potential revenue from selling servers, and available money. Each data center has its own resources, and money cannot be transferred between them.

For each data center, the input arrays provide:

  • count[i]: the total number of servers at the i-th data center.
  • upgrade[i]: the cost to upgrade a single server at the i-th data center.
  • sell[i]: the money gained by selling a single server at the i-th data center.
  • money[i]: the initial available money at the i-th data center.

The task is to determine the maximum number of servers that can be upgraded, optionally selling some servers to increase available money, and respecting the constraint that no data center can spend more than its available resources.

Constraints indicate that all arrays have a length up to 100,000, and values can also reach 100,000. This rules out any naive solution that tries all possible selling counts one by one, as it would be too slow for the upper limit.

Important edge cases include:

  • When money is insufficient to upgrade even one server without selling.
  • When selling all servers is cheaper than upgrading any.
  • When the cost of upgrading is smaller than the money available, so selling is unnecessary.
  • Minimum input size, n = 1.

Approaches

The brute-force approach would attempt every possible number of servers to sell, calculate the resulting money, and check how many servers could then be upgraded. For each data center with count[i] servers, this could require up to count[i] calculations, leading to O(n * max(count[i])) time complexity. For large counts, this is too slow.

The key observation is that for a given data center, if we sell x servers, the total money becomes money[i] + x * sell[i], and the number of servers left to upgrade is count[i] - x. The maximum number of servers we can upgrade is bounded by the money available divided by the upgrade cost, i.e., min(count[i] - x, (money[i] + x * sell[i]) // upgrade[i]).

Since the function f(x) = min(count[i] - x, (money[i] + x * sell[i]) // upgrade[i]) is monotonic with respect to x, we can use binary search on x to find the optimal number of servers to sell for each data center.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * max(count[i])) O(1) Try all possible number of servers to sell for each data center
Optimal O(n * log(count[i])) O(1) Binary search on the number of servers to sell for each data center

Algorithm Walkthrough

  1. Initialize an empty list answer to store the maximum upgradable servers for each data center.
  2. Iterate over each data center with index i.
  3. For each data center, define low = 0 and high = count[i]. low represents selling 0 servers, and high represents selling all servers.
  4. Perform binary search:
  • Calculate mid = (low + high) // 2, representing selling mid servers.
  • Compute remaining servers: remaining = count[i] - mid.
  • Compute available money: available_money = money[i] + mid * sell[i].
  • Compute the number of servers we can upgrade with available money: upgradable = available_money // upgrade[i].
  • The feasible number of upgrades is min(remaining, upgradable).
  • If upgradable >= remaining, then we can potentially sell fewer servers, set high = mid - 1. Otherwise, we need to sell more servers, set low = mid + 1.
  1. After binary search, low or high (whichever maximizes upgrades) gives the optimal number of servers to sell. Calculate the corresponding upgradable servers and append to answer.
  2. Return answer.

Why it works: The binary search works because the maximum upgradable servers is a monotonic function with respect to the number of servers sold. Selling more servers increases available money but decreases servers to upgrade. The maximum occurs at a point where these two effects balance.

Python Solution

from typing import List

class Solution:
    def maxUpgrades(self, count: List[int], upgrade: List[int], sell: List[int], money: List[int]) -> List[int]:
        answer = []
        n = len(count)
        for i in range(n):
            low, high = 0, count[i]
            max_upgrade = 0
            while low <= high:
                mid = (low + high) // 2
                remaining = count[i] - mid
                available_money = money[i] + mid * sell[i]
                upgradable = available_money // upgrade[i]
                feasible = min(remaining, upgradable)
                max_upgrade = max(max_upgrade, feasible)
                if upgradable >= remaining:
                    high = mid - 1
                else:
                    low = mid + 1
            answer.append(max_upgrade)
        return answer

Implementation Explanation: For each data center, binary search finds the number of servers to sell that maximizes upgrades. At each iteration, we calculate the feasible number of upgrades considering both remaining servers and available money. The maximum feasible upgrades over all possible sells is appended to the answer.

Go Solution

func maxUpgrades(count []int, upgrade []int, sell []int, money []int) []int {
    n := len(count)
    answer := make([]int, n)
    for i := 0; i < n; i++ {
        low, high := 0, count[i]
        maxUpgrade := 0
        for low <= high {
            mid := (low + high) / 2
            remaining := count[i] - mid
            availableMoney := money[i] + mid*sell[i]
            upgradable := availableMoney / upgrade[i]
            feasible := upgradable
            if feasible > remaining {
                feasible = remaining
            }
            if feasible > maxUpgrade {
                maxUpgrade = feasible
            }
            if upgradable >= remaining {
                high = mid - 1
            } else {
                low = mid + 1
            }
        }
        answer[i] = maxUpgrade
    }
    return answer
}

Go Implementation Notes: Go handles integer division automatically, and slices are initialized with make. Logic mirrors the Python version closely, with care taken for integer arithmetic and assignment to slices.

Worked Examples

Example 1: count = [4,3], upgrade = [3,5], sell = [4,2], money = [8,9]

For the first data center:

Sold Remaining Available Money Upgradable Feasible
0 4 8 2 2
1 3 12 4 3
2 2 16 5 2

Maximum upgrades = 3

For the second data center:

Sold Remaining Available Money Upgradable Feasible
0 3 9 1 1
1 2 11 2 2
2 1 13 2 1

Maximum upgrades = 2

Output: [3,2]

Example 2: count = [1], upgrade = [2], sell = [1], money = [1]

Sold Remaining Available Money Upgradable Feasible
0 1 1 0 0
1 0 2 1 0

Maximum upgrades = 0

Output: [0]

Complexity Analysis

Measure Complexity Explanation
Time O(n * log(max(count))) Binary search on each data center over at most count[i] servers
Space O(n) Storing the result in answer array

The binary search reduces what would otherwise be a linear scan over count[i] servers to logarithmic time per data center.

Test Cases

# Provided examples
assert Solution().maxUpgrades([4,3],[3,5],[4,2],[8,9]) == [3,2]  # Example 1
assert Solution().maxUpgrades([1],[2],[1],[1]) == [0]           # Example 2

# Edge cases
assert Solution().maxUpgrades([1],[1],[1],[1]) == [1]           # Can upgrade without selling
assert Solution().maxUpgrades([10],[5],[1],[3]) == [0]          # Cannot upgrade even selling all
assert Solution().maxUpgrades([5],[2],[2],[0]) == [2