Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
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

Solution

Method 1 – Binary Search on Number of Upgrades

Intuition

For each data center, we want to maximize the number of servers we can upgrade, possibly by selling some servers to get more money. For a given number of upgrades k, we can sell up to count - k servers. We check if the money after selling is enough to upgrade k servers. We use binary search to find the maximum k for each data center.

Approach

  1. For each data center:
    • Use binary search for k from 0 to count (number of servers).
    • For each k, calculate:
      • Servers to sell: count - k
      • Money after selling: money + sell * (count - k)
      • Cost to upgrade: upgrade * k
    • If money after selling is at least the cost to upgrade, k is possible.
    • Find the largest such k using binary search.
  2. Return the answer for all data centers.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<int> maxUpgrade(vector<int>& count, vector<int>& upgrade, vector<int>& sell, vector<int>& money) {
        int n = count.size();
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            int l = 0, r = count[i], res = 0;
            while (l <= r) {
                int k = (l + r) / 2;
                long long have = 1LL * money[i] + 1LL * sell[i] * (count[i] - k);
                long long need = 1LL * upgrade[i] * k;
                if (have >= need) { res = k; l = k + 1; }
                else r = k - 1;
            }
            ans[i] = res;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func maxUpgrade(count, upgrade, sell, money []int) []int {
    n := len(count)
    ans := make([]int, n)
    for i := 0; i < n; i++ {
        l, r, res := 0, count[i], 0
        for l <= r {
            k := (l + r) / 2
            have := int64(money[i]) + int64(sell[i]) * int64(count[i]-k)
            need := int64(upgrade[i]) * int64(k)
            if have >= need {
                res = k
                l = k + 1
            } else {
                r = k - 1
            }
        }
        ans[i] = res
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int[] maxUpgrade(int[] count, int[] upgrade, int[] sell, int[] money) {
        int n = count.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int l = 0, r = count[i], res = 0;
            while (l <= r) {
                int k = (l + r) / 2;
                long have = (long)money[i] + (long)sell[i] * (count[i] - k);
                long need = (long)upgrade[i] * k;
                if (have >= need) { res = k; l = k + 1; }
                else r = k - 1;
            }
            ans[i] = res;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    fun maxUpgrade(count: IntArray, upgrade: IntArray, sell: IntArray, money: IntArray): IntArray {
        val n = count.size
        val ans = IntArray(n)
        for (i in 0 until n) {
            var l = 0
            var r = count[i]
            var res = 0
            while (l <= r) {
                val k = (l + r) / 2
                val have = money[i].toLong() + sell[i].toLong() * (count[i] - k)
                val need = upgrade[i].toLong() * k
                if (have >= need) {
                    res = k
                    l = k + 1
                } else {
                    r = k - 1
                }
            }
            ans[i] = res
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def maxUpgrade(self, count: list[int], upgrade: list[int], sell: list[int], money: list[int]) -> list[int]:
        n = len(count)
        ans = []
        for i in range(n):
            l, r, res = 0, count[i], 0
            while l <= r:
                k = (l + r) // 2
                have = money[i] + sell[i] * (count[i] - k)
                need = upgrade[i] * k
                if have >= need:
                    res = k
                    l = k + 1
                else:
                    r = k - 1
            ans.append(res)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn max_upgrade(count: Vec<i32>, upgrade: Vec<i32>, sell: Vec<i32>, money: Vec<i32>) -> Vec<i32> {
        let n = count.len();
        let mut ans = vec![0; n];
        for i in 0..n {
            let (mut l, mut r, mut res) = (0, count[i], 0);
            while l <= r {
                let k = (l + r) / 2;
                let have = money[i] as i64 + sell[i] as i64 * (count[i] as i64 - k as i64);
                let need = upgrade[i] as i64 * k as i64;
                if have >= need {
                    res = k;
                    l = k + 1;
                } else {
                    r = k - 1;
                }
            }
            ans[i] = res;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    maxUpgrade(count: number[], upgrade: number[], sell: number[], money: number[]): number[] {
        const n = count.length, ans: number[] = [];
        for (let i = 0; i < n; i++) {
            let l = 0, r = count[i], res = 0;
            while (l <= r) {
                const k = Math.floor((l + r) / 2);
                const have = money[i] + sell[i] * (count[i] - k);
                const need = upgrade[i] * k;
                if (have >= need) {
                    res = k;
                    l = k + 1;
                } else {
                    r = k - 1;
                }
            }
            ans.push(res);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log m) — For each data center, binary search over up to count[i] servers.
  • 🧺 Space complexity: O(n) — For the answer array.