# Maximum Running Time of N Computers
## Problem Statement
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`\
## Intuition
```
Basically, if mid = 5, Directly if arr[i] is 7,
It can power for 5min, So We consider it to be 5 for average calculatons
1 2 3 4 5 .........1e5
We can at each step who gives us the answer shift range accordingly
How to decide if certain mid is satisfying
2 4 4 6 7
if mid = 5
6 and 7 can satisfy for 5min
But 2 4 4 have to combinely satisfy for 5 min
So we find average 2+4+4 +5+5(for 6 and 7) for not affecting average
and check if average/n >= mid
Basically at each point we find out if the batteries can combinely on average
support n computers, if not we lower time(mid) and check for that,
Else we go ahead
```
### Links
### Video Links
### Approach 1:
```
Binary Search over entire Answer Space
```
{% code title="C++" lineNumbers="true" %}
```cpp
class Solution {
public:
bool check(vector& arr, long long time, int n){
long long avg = 0;
for(auto &cur_time: arr){
if(cur_time < time)
avg += cur_time;
else
avg += time;
}
return avg >= n*time;
}
long long maxRunTime(int n, vector& arr) {
long long ans = 0;
long long low = 0;
long long high;
for(auto &it: arr)
high += it;
while(low<=high){
long long mid = low + (high-low)/2;
if( check(arr,mid,n) ){
ans = mid;
low = mid+1;
}
else
high = mid-1;
}
return ans;
}
};
```
{% endcode %}
### Approach 2:
```
```
{% code title="C++" lineNumbers="true" %}
```cpp
```
{% endcode %}
### Approach 3:
```
```
{% code title="C++" lineNumbers="true" %}
```cpp
```
{% endcode %}
### Similar Problems