##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2141.html

# 2141. Maximum Running Time of N Computers

• Difficulty: Hard.
• Related Topics: Array, Binary Search, Greedy, Sorting.
• Similar Questions: Minimum Moves to Equal Array Elements, Sell Diminishing-Valued Colored Balls, Maximum Number of Tasks You Can Assign, Minimum Time to Complete Trips, Minimum Amount of Time to Fill Cups.

## Problem

You have n computers. You are given the integer n and a 0-indexed integer array batteries where the ith battery can run a computer for batteries[i] minutes. You are interested in running all n computers simultaneously using the given batteries.

Initially, you can insert at most one battery into each computer. After that and at any integer time moment, you can remove a battery from a computer and insert another battery any number of times. The inserted battery can be a totally new battery or a battery from another computer. You may assume that the removing and inserting processes take no time.

Note that the batteries cannot be recharged.

Return the **maximum number of minutes you can run all the n computers simultaneously.**

Example 1:

Input: n = 2, batteries = [3,3,3]
Output: 4
Explanation:
Initially, insert battery 0 into the first computer and battery 1 into the second computer.
After two minutes, remove battery 1 from the second computer and insert battery 2 instead. Note that battery 1 can still run for one minute.
At the end of the third minute, battery 0 is drained, and you need to remove it from the first computer and insert battery 1 instead.
By the end of the fourth minute, battery 1 is also drained, and the first computer is no longer running.
We can run the two computers simultaneously for at most 4 minutes, so we return 4.



Example 2:

Input: n = 2, batteries = [1,1,1,1]
Output: 2
Explanation:
Initially, insert battery 0 into the first computer and battery 2 into the second computer.
After one minute, battery 0 and battery 2 are drained so you need to remove them and insert battery 1 into the first computer and battery 3 into the second computer.
After another minute, battery 1 and battery 3 are also drained so the first and second computers are no longer running.
We can run the two computers simultaneously for at most 2 minutes, so we return 2.


Constraints:

• 1 <= n <= batteries.length <= 105

• 1 <= batteries[i] <= 109

## Solution

• class Solution {
private boolean isPossibeToRun(int n, int[] batteries, long avgTime) {
long duration = 0;
for (long ele : batteries) {
duration += Math.min(ele, avgTime);
}
return avgTime * n <= duration;
}

public long maxRunTime(int n, int[] batteries) {
long startTime = 0;
long sum = 0;
long ans = 0;
for (long ele : batteries) {
sum += ele;
}
long endTime = sum;
while (startTime <= endTime) {
long avgTime = (startTime + endTime) / 2;
if (isPossibeToRun(n, batteries, avgTime)) {
ans = avgTime;
startTime = avgTime + 1;
} else {
endTime = avgTime - 1;
}
}
return ans;
}
}

• # 2141. Maximum Running Time of N Computers
# https://leetcode.com/problems/maximum-running-time-of-n-computers

class Solution:
def maxRunTime(self, n: int, batteries: List[int]) -> int:

def good(k):
target = n * k
have = 0

for x in batteries:
have += min(x, k)

return have >= target

total = sum(batteries)

left, right = 0, total // n
res = -1

while left <= right:
mid = left + (right - left) // 2

if good(mid):
res = mid
left = mid + 1
else:
right = mid - 1

return res


• impl Solution {
pub fn max_run_time(n: i32, batteries: Vec<i32>) -> i64 {

// First sort the batteries
let mut batteries = batteries;
let m = batteries.len() as i32;
batteries.sort();

let mut extra_sum: i64 = 0;
for i in 0..(m - n) as usize {
extra_sum += batteries[i] as i64;
}

let mut i = (m - n) as usize;
let mut cur_height = batteries[i];
let mut ret = cur_height as i64;
while extra_sum != 0 {
if i + 1 == m as usize {
assert!(cur_height == *batteries.last().unwrap());
ret += extra_sum / n as i64;
break;
}

if batteries[i] == batteries[i + 1] {
i += 1;
continue;
}

let diff = extra_sum / (i - (m - n) as usize + 1) as i64;

if (cur_height as i64 + diff) <= batteries[i + 1] as i64 {
ret = cur_height as i64 + diff;
break;
} else {
extra_sum -= (batteries[i + 1] - batteries[i]) as i64 * (i - (m - n) as usize + 1) as i64;
ret = batteries[i + 1] as i64;
}

i += 1;
if i != m as usize {
cur_height = batteries[i];
}
}

ret
}
}

• class Solution {
public:
long long maxRunTime(int n, vector<int>& batteries) {
long long l = 0, r = 0;
for (int x : batteries) {
r += x;
}
while (l < r) {
long long mid = (l + r + 1) >> 1;
long long s = 0;
for (int x : batteries) {
s += min(1LL * x, mid);
}
if (s >= n * mid) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
};

• func maxRunTime(n int, batteries []int) int64 {
l, r := 0, 0
for _, x := range batteries {
r += x
}
for l < r {
mid := (l + r + 1) >> 1
s := 0
for _, x := range batteries {
s += min(x, mid)
}
if s >= n*mid {
l = mid
} else {
r = mid - 1
}
}
return int64(l)
}

func min(a, b int) int {
if a < b {
return a
}
return b
}

• function maxRunTime(n: number, batteries: number[]): number {
let l = 0n;
let r = 0n;
for (const x of batteries) {
r += BigInt(x);
}
while (l < r) {
const mid = (l + r + 1n) >> 1n;
let s = 0n;
for (const x of batteries) {
s += BigInt(Math.min(x, Number(mid)));
}
if (s >= mid * BigInt(n)) {
l = mid;
} else {
r = mid - 1n;
}
}
return Number(l);
}



Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).