# 2141. Maximum Running Time of N Computers

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public: long long maxRunTime(int n, vector& batteries) { long long sum = accumulate(begin(batteries), end(batteries), 0LL); sort(begin(batteries), end(batteries)); // max battery is greater than the average, so it can last forever // reduce the problem from size n to size n - 1 while (batteries.back() > sum / n) { sum -= batteries.back(), batteries.pop_back(); --n; } // if the max battery <= average running time, // it won't be waste, and so do smaller batteries return sum / n; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public long maxRunTime(int n, int[] batteries) { long sum = Arrays.stream(batteries).asLongStream().sum(); Arrays.sort(batteries); // max battery is greater than the average, so it can last forever // reduce the problem from size n to size n - 1 int i = batteries.length - 1; while (batteries[i] > sum / n) { sum -= batteries[i--]; --n; } // if the max battery <= average running time, // it won't be waste, and so do smaller batteries return sum / n; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution: def maxRunTime(self, n: int, batteries: List[int]) -> int: summ = sum(batteries) batteries.sort() # max battery is greater than the average, so it can last forever # reduce the problem from size n to size n - 1 while batteries[-1] > summ // n: summ -= batteries.pop() n += 1 # if the max battery <= average running time, # it won't be waste, and so do smaller batteries return summ // n