2141. Maximum Running Time of N Computers LeetCode Solution

In this guide, you will get 2141. Maximum Running Time of N Computers LeetCode Solution with the best time and space complexity. The solution to Maximum Running Time of N Computers problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Maximum Running Time of N Computers solution in C++
4. Maximum Running Time of N Computers solution in Java
5. Maximum Running Time of N Computers solution in Python
6. Additional Resources

Problem Statement of Maximum Running Time of N Computers

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

Complexity Analysis

• Time Complexity: O(\texttt{sort})
• Space Complexity: O(1)

2141. Maximum Running Time of N Computers LeetCode Solution in C++

class Solution {
 public:
  long long maxRunTime(int n, vector<int>& batteries) {
    long sum = accumulate(batteries.begin(), batteries.end(), 0L);

    ranges::sort(batteries);

    // The maximum 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 maximum battery <= average running time, it won't be waste, and so
    // do smaller batteries.
    return sum / n;
  }
};
/* code provided by PROGIEZ */

2141. Maximum Running Time of N Computers LeetCode Solution in Java

class Solution {
  public long maxRunTime(int n, int[] batteries) {
    long sum = Arrays.stream(batteries).asLongStream().sum();

    Arrays.sort(batteries);

    // The maximum 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 maximum battery <= average running time, it won't be waste, and so
    // do smaller batteries.
    return sum / n;
  }
}
// code provided by PROGIEZ

2141. Maximum Running Time of N Computers LeetCode Solution in Python

class Solution:
  def maxRunTime(self, n: int, batteries: list[int]) -> int:
    summ = sum(batteries)

    batteries.sort()

    # The maximum 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 maximum battery <= average running time, it won't be waste, and so
    # do smaller batteries.
    return summ // n
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.