Maximum Running Time of N Computers

Hard

#1951Time: O(m * log H), where `m` is the number of batteries and `H` is the range of the search space for the answer (from 0 to `sum(batteries)/n`). The `canRun` function takes O(m) time, and it's called O(log H) times by the binary search.Space: O(1), as we only use a few variables to store the search boundaries and the answer.2 companies

Patterns

Greedy

Algorithms

Binary Search Sorting

Data structures

Array

Companies

Deutsche Bank Flipkart

Prompt

You have n computers. You are given the integer n and a 0-indexed integer array batteries where the i^th 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 <= 10⁵
1 <= batteries[i] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

A standard approach for problems that ask to maximize a value is to binary search for the answer. We can guess a time T and then check if it's possible to run all n computers for this duration. The key insight is that if we can run the computers for T minutes, we can also run them for any duration less than T. This monotonicity allows us to use binary search.

The check function, canRun(T), determines feasibility. To run n computers for T minutes, we need a total of n * T minutes of power. Each battery b_i can contribute at most min(b_i, T) minutes. Thus, we can run for T minutes if the sum of contributions from all batteries is at least the required amount.

Algorithm

The problem asks for the maximum possible running time. This structure suggests that we can use binary search on the answer. If we can run all computers for a time T, we can certainly run them for any time T' < T. This monotonic property allows for binary search.
We need to define a function, let's call it canRun(time), that returns true if it's possible to run n computers simultaneously for time minutes, and false otherwise.
To determine if canRun(time) is true, we consider the total power contribution from all batteries. For a target duration of time, a single battery with capacity b can contribute at most min(b, time) to the total power supply. This is because a battery cannot supply more power than its capacity (b), and its contribution is capped at time since it can only power one computer at a time.
The total power required to run n computers for time minutes is n * time.
Therefore, the condition for canRun(time) to be true is: sum(min(battery, time) for battery in batteries) >= n * time.
We can binary search for the largest time that satisfies this condition.

Binary Search Steps:

Define a search range [low, high]. low can be 0. A safe upper bound for high can be the sum of all battery capacities divided by n, or simply a very large number like 10^14 to be safe.
While low <= high: a. Calculate mid = low + (high - low) / 2. b. Check if canRun(mid) is true. c. If it is, mid is a possible answer. We try for a larger time, so we set ans = mid and low = mid + 1. d. If it's not, mid is too large. We need to try a smaller time, so we set high = mid - 1.
The final value stored in ans will be the maximum possible time.

Walkthrough

1class Solution {2    public long maxRunTime(int n, int[] batteries) {3        long low = 0;4        long high = 0;5        for (int b : batteries) {6            high += b;7        }8        // A reasonable upper bound for the search space.9        // The total time cannot exceed the average time if all power is pooled.10        high /= n;11        12        long ans = 0;13        14        while (low <= high) {15            long mid = low + (high - low) / 2;16            if (canRun(n, batteries, mid)) {17                ans = mid;18                low = mid + 1;19            } else {20                high = mid - 1;21            }22        }23        return ans;24    }25    26    // Checks if we can run n computers for a given 'time'.27    private boolean canRun(int n, int[] batteries, long time) {28        if (time == 0) return true;29        long totalPowerSupplied = 0;30        // Each battery can supply at most 'time' minutes of power to the system.31        for (int b : batteries) {32            totalPowerSupplied += Math.min((long)b, time);33        }34        // The total power supplied must be at least the total power required.35        return totalPowerSupplied >= (long)n * time;36    }37}

Complexity

Time

O(m * log H), where `m` is the number of batteries and `H` is the range of the search space for the answer (from 0 to `sum(batteries)/n`). The `canRun` function takes O(m) time, and it's called O(log H) times by the binary search.

Space

O(1), as we only use a few variables to store the search boundaries and the answer.

Trade-offs

Pros

Conceptually straightforward and a common pattern for optimization problems.
Guaranteed to find the optimal solution due to the monotonic nature of the canRun function.

Cons

Slightly less efficient than the greedy approach due to the repeated scanning of the batteries array within the binary search loop.

A more efficient solution uses a greedy approach. The intuition is that if we have more batteries than computers, the smallest batteries will inevitably be depleted. We can treat these smallest batteries as a collective power bank. The n largest batteries can be assigned to the n computers. Then, we use the power from the collective bank to sequentially 'level up' the charge of the computers, starting from the one with the least powerful battery. We continue this process until we run out of extra power or have leveled all computers to the same battery level. The final level represents the maximum running time.

Algorithm

Sort the batteries array in ascending order.
If there are more batteries than computers (m > n), the m-n smallest batteries can be considered an 'extra' power source. Sum their capacities into a variable extraPower.
The remaining n largest batteries are our primary power sources, one for each computer. Let's call them liveBatteries (which are batteries[m-n] to batteries[m-1] in the sorted array).
The core idea is to use extraPower to 'level up' the liveBatteries so they all last for the same amount of time. We iterate through the liveBatteries from smallest to largest.
For each i from 0 to n-2, we calculate the power needed to raise the first i+1 batteries (which are all conceptually at the level of liveBatteries[i]) to the level of the next battery, liveBatteries[i+1]. The power needed is (i+1) * (liveBatteries[i+1] - liveBatteries[i]).
If extraPower is sufficient, we subtract the needed amount and proceed to the next battery.
If extraPower is insufficient, we cannot level up to liveBatteries[i+1]. The maximum time is the current level liveBatteries[i] plus the remaining extraPower distributed evenly among the i+1 computers. The result is liveBatteries[i] + extraPower / (i+1).
If the loop completes, it means we have successfully leveled all n batteries to the capacity of the largest one, liveBatteries[n-1]. Any remaining extraPower can be distributed evenly among all n computers. The result is liveBatteries[n-1] + extraPower / n.

Walkthrough

1import java.util.Arrays;2 3class Solution {4    public long maxRunTime(int n, int[] batteries) {5        // Sort batteries to easily identify the smallest and largest ones.6        Arrays.sort(batteries);7        int m = batteries.length;8        9        // The first m-n batteries are considered extra. Sum their power.10        long extraPower = 0;11        for (int i = 0; i < m - n; i++) {12            extraPower += batteries[i];13        }14        15        // The n largest batteries are at indices m-n to m-1.16        // We will try to level them up using the extra power.17        for (int i = m - n; i < m - 1; i++) {18            // Number of computers we are currently leveling up.19            long numComputers = i - (m - n) + 1;20            // Difference in power to the next level.21            long diff = batteries[i+1] - batteries[i];22            // Power needed to bring all 'numComputers' to the next level.23            long needed = numComputers * diff;24            25            if (extraPower < needed) {26                // Not enough extra power to reach the next level.27                // Distribute the remaining extra power evenly.28                return batteries[i] + extraPower / numComputers;29            }30            31            // Sufficient power, so we level up and decrease extra power.32            extraPower -= needed;33        }34        35        // If we exit the loop, all n computers have been leveled to the36        // capacity of the largest battery. Distribute any remaining extra power.37        return batteries[m-1] + extraPower / n;38    }39}

Complexity

Time

O(m log m), where `m` is the number of batteries. The complexity is dominated by the initial sorting of the `batteries` array. The subsequent loops run in O(m) time.

Space

O(log m) or O(1), depending on the implementation of the sorting algorithm. `Arrays.sort` in Java for primitives uses a dual-pivot quicksort which has an average space complexity of O(log m).

Trade-offs

Pros

This is the most efficient approach, with a time complexity dominated by sorting.
It uses constant extra space (if the sort is in-place).

Cons

The greedy logic can be less intuitive to come up with compared to the binary search approach.

Solutions

Solution

1class Solution {2public3  long maxRunTime(int n, int[] batteries) {4    long l = 0, r = 0;5    for (int x : batteries) {6      r += x;7    }8    while (l < r) {9      long mid = (l + r + 1) >> 1;10      long s = 0;11      for (int x : batteries) {12        s += Math.min(mid, x);13      }14      if (s >= n * mid) {15        l = mid;16      } else {17        r = mid - 1;18      }19    }20    return l;21  }22}

1class Solution {2public:3  long long maxRunTime(int n, vector<int> &batteries) {4    long long l = 0, r = 0;5    for (int x : batteries) {6      r += x;7    }8    while (l < r) {9      long long mid = (l + r + 1) >> 1;10      long long s = 0;11      for (int x : batteries) {12        s += min(1LL * x, mid);13      }14      if (s >= n * mid) {15        l = mid;16      } else {17        r = mid - 1;18      }19    }20    return l;21  }22};

1class Solution:2    def maxRunTime(self, n: int, batteries: List[int]) -> int: l, r = 0, sum(batteries) while l < r: mid = (l + r + 1) >> 1 if sum(min(x, mid) for x in batteries) >= n * mid: l = mid else: r = mid - 1 return l

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem