Maximum Running Time of N Computers

89.7k
0

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 swapped battery can be a totally new battery or a battery from another computer. You may assume that the swapping process takes no time.

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 computer 1 and battery 1 into computer 2. After 2 minutes, remove battery 1 from computer 2 and insert battery 2 instead. After another 1 minute, battery 0 becomes empty. Remove it and insert battery 1 instead. After another 1 minute, battery 1 and battery 2 become empty. Both computers stop. We can run the computers simultaneously for 4 minutes.

Example 2

Input: N = 2, batteries = [1, 1, 1, 1]

Output: 2

Explanation: Insert battery 0 into computer 1 and battery 1 into computer 2. After 1 minute, both batteries become empty. Insert battery 2 into computer 1 and battery 3 into computer 2. After another 1 minute, both batteries become empty. We can run the computers simultaneously for 2 minutes.

Brute Force Approach

The most direct idea is to try every possible running time. For a chosen time X, all N computers need a total of N x X battery minutes. But there is one important limit. A single battery with power greater than X still contributes only X useful minutes for this check, because it cannot run more than one computer at the same time during those X minutes.

So for every battery, the useful contribution is: min(battery, X)

If the total useful contribution from all batteries is at least N x X, then running all computers for X minutes is possible. The brute force approach checks X = 0, 1, 2, ... until the time no longer works.

Algorithm

  • First, find the total battery time. The maximum answer cannot be more than total / N, because N computers running for X minutes need N x X total minutes.

  • Try each possible running time from 0 to total / N. This is easy to understand because it checks the answer in increasing order.

  • For each chosen time, add min(battery, time) for every battery. This is done because a battery cannot usefully contribute more than the chosen running time.

  • If the total useful contribution is at least N x time, the chosen time works, so store it as the current best answer.

  • If a chosen time does not work, stop and return the best answer found so far. Larger times will also fail because they need even more total battery minutes.

Dry Run

Maximum Running Time of N Computers Brute Dry Run

Maximum Running Time of N Computers Brute Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Checks whether all n computers can run
for the given time using the batteries.
*/
bool canRun(int n, vector<int>& batteries, long long time) {
// This is the total useful battery time needed.
long long required = (long long)n * time;
// This stores useful battery time available for this target.
long long available = 0;
for (int battery : batteries) {
// A battery cannot help more than time minutes
// for this target running time.
available += min((long long)battery, time);
// Enough useful power has been found,
// so checking more batteries is unnecessary.
if (available >= required) {
return true;
}
}
// The target time works only if enough useful power exists.
return available >= required;
}
/*
Returns the maximum running time by
checking every possible time one by one.
*/
long long maxRunTime(int n, vector<int>& batteries) {
// This stores the total battery minutes available.
long long total = 0;
for (int battery : batteries) {
total += battery;
}
// No answer can be larger than total battery time divided by n.
long long high = total / n;
// This stores the largest working time found so far.
long long answer = 0;
for (long long time = 0; time <= high; time++) {
// If this time works, it becomes the current best answer.
if (canRun(n, batteries, time)) {
answer = time;
} else {
// Once a time fails, every larger time will also fail.
return answer;
}
}
return answer;
}
};
// Driver code starts
int main() {
int n = 2;
vector<int> batteries = {3, 3, 3};
Solution obj;
cout << obj.maxRunTime(n, batteries) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(B x (Total / N)), where B is the number of batteries, because every possible time may scan all batteries, with Total = sum of all batteries.

Space Complexity: O(1), because constant space is used.

Optimal Approach

The key observation is that it is monotonic. If all computers can run for X minutes, then they can definitely run for any shorter time too. If all computers cannot run for X minutes, then they cannot run for any larger time either, because a larger time needs even more total battery power.

So the possible running times look like this: possible, possible, possible, not possible, not possible

The answer is the largest possible time. To check one target time, calculate how much useful power the batteries can provide. A battery with battery minutes contributes: min(battery, targetTime)

This cap matters because during targetTime minutes, one battery cannot power more than one computer at the same time. Extra power beyond targetTime from a single battery cannot be counted twice in that same time window.

If the total useful power is at least N × targetTime, then that target time is possible.

Algorithm

  • Find the total battery time and set the search range from 0 to total / N. This upper bound is valid because running N computers for more than total / N minutes would require more battery time than exists.

  • Pick the middle running time from the current search range. This is the target time being tested.

  • For this target time, add min(battery, targetTime) for every battery. This counts only the useful contribution each battery can make during that time.

  • If the useful contribution is at least N × targetTime, the target time works. Store it and move right because the goal is to maximize runtime.

  • If the useful contribution is smaller than N × targetTime, the target time is too large. Move left because larger times will need even more power.

  • When binary search ends, return the largest working time stored.

Dry Run

Maximum Running Time of N Computers Optimal Dry Run

Maximum Running Time of N Computers Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Checks whether all n computers can run
for the given time using the batteries.
*/
bool canRun(int n, vector<int>& batteries, long long time) {
// This is the total useful battery time needed.
long long required = (long long)n * time;
// This stores useful battery time available for this target.
long long available = 0;
for (int battery : batteries) {
// A battery cannot help more than time minutes
// for this target running time.
available += min((long long)battery, time);
// Enough useful power has been found,
// so checking more batteries is unnecessary.
if (available >= required) {
return true;
}
}
// The target time works only if enough useful power exists.
return available >= required;
}
/*
Returns the maximum running time using
binary search on possible running times.
*/
long long maxRunTime(int n, vector<int>& batteries) {
// This stores the total battery minutes available.
long long total = 0;
for (int battery : batteries) {
total += battery;
}
// Zero minutes is always possible.
long long low = 0;
// No answer can be larger than total battery time divided by n.
long long high = total / n;
// This stores the largest working time found so far.
long long answer = 0;
while (low <= high) {
// mid is the running time currently being tested.
long long mid = low + (high - low) / 2;
// If mid works, search right to try for more minutes.
if (canRun(n, batteries, mid)) {
answer = mid;
low = mid + 1;
} else {
// If mid does not work, larger times will also fail.
high = mid - 1;
}
}
return answer;
}
};
// Driver code starts
int main() {
int n = 2;
vector<int> batteries = {3, 3, 3};
Solution obj;
cout << obj.maxRunTime(n, batteries) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(B × log2(Total / N)), where B is the number of batteries, because each binary-search check scans all batteries and binary search has a possible answer range of 1 to Total / N, with Total = sum of all batteries.

Space Complexity: O(1), because constant space is used.

Interview follow-up Questions

A single battery can power only one computer at any exact moment. Even if a battery contains 1000 minutes of power, if you only plan to keep the computers running for 10 minutes, that battery can only offer 10 minutes of active use. The remaining power cannot be distributed across multiple computers at the exact same time.

Two PointerSortingMathsBinary SearchArrays

Read Similar Blogs

Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then sec...

61.7k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cells are mat[0][0...

67.1k
Arrays

Search Element in Matrix

Given a matrix with N rows and M columns and a target value X , search for X in the matrix. Return the position of the first occurrence of X as {row, col} . Return {-1, -1} when the target value is...

98.4k
Comments0