We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Upgradable Servers

Number: 3458

Difficulty: Medium

Paid? Yes

Companies: Snowflake

Problem Description

You are given four arrays—count, upgrade, sell, and money—each representing a data center's state. For each data center, count[i] denotes the total number of servers, upgrade[i] denotes the cost to upgrade a single server, sell[i] denotes the money obtained by selling a server, and money[i] is the initial money available. You may sell some servers (earning sell[i] each) and then use the combined funds to upgrade the remaining servers (costing upgrade[i] each). Determine the maximum number of servers that can be upgraded for each data center. Note that the money from one data center cannot be used in another.

Key Insights

  • For a given data center with count servers, if you choose to upgrade x servers, you must sell (count - x) servers.
  • After selling, the available money becomes money + (count - x) * sell.
  • To upgrade x servers, the required money is x * upgrade.
  • The inequality becomes: money + (count - x) * sell >= x * upgrade.
  • Rearranging the inequality gives: money + count * sell >= x * (upgrade + sell).
  • Therefore, the maximum upgradable servers is x = floor((money + count * sell) / (upgrade + sell)), capped by count.
  • Use a mathematical derivation rather than binary search to achieve O(n) time per data center.

Space and Time Complexity

Time Complexity: O(n), where n is the number of data centers (each is processed in constant time).
Space Complexity: O(n) for storing the output array.

Solution

For each data center, compute:   candidate = (money + count * sell) // (upgrade + sell) Then, the answer for that data center is the minimum between count and candidate.
This is based on rearranging the equation: money + (count - x) * sell >= x * upgrade, which leads to x <= (money + count * sell) / (upgrade + sell).
Thus, by taking the floor value and ensuring we do not exceed count, we achieve the optimal solution.

Code Solutions

# Python solution for "Maximum Number of Upgradable Servers"
def max_upgradable_servers(count, upgrade, sell, money):
    # Number of data centers
    n = len(count)
    # Initialize the answer list with zeros
    answer = [0] * n
    
    # Iterate over each data center
    for i in range(n):
        # Calculate the maximum servers that can be upgraded based on available money after selling
        candidate = (money[i] + count[i] * sell[i]) // (upgrade[i] + sell[i])
        # Ensure that the candidate does not exceed the total count of servers
        answer[i] = min(count[i], candidate)
    
    return answer

# Example usage:
# data center 1: count=4, upgrade=3, sell=4, money=8
# data center 2: count=3, upgrade=5, sell=2, money=9
print(max_upgradable_servers([4, 3], [3, 5], [4, 2], [8, 9]))  # Output: [3,2]
← Back to All Questions