# 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
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://coding-9.gitbook.io/untitled/binary-search/bs-over-answer-space-answer-space/maximum-running-time-of-n-computers.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.