Maximum Running Time of N Computers - Practice Coding Problems

Maximum Running Time of N Computers - Problem

You have n computers and are given an integer array batteries where batteries[i] represents the number of minutes the i-th battery can power a computer.

Your goal is to run all n computers simultaneously for the maximum possible time using the available batteries.

Rules:

Initially, you can insert at most one battery into each computer
At any time, you can remove a battery and insert another battery (takes no time)
You can move batteries between computers freely
Batteries cannot be recharged

Return the maximum number of minutes you can run all n computers simultaneously.

Input & Output

Example 1 — Basic Case

$ Input: n = 2, batteries = [3,3,3,1]

› Output: 5

💡 Note: We can run 2 computers for 5 minutes. Total power needed = 2×5 = 10. Available power = min(3,5)+min(3,5)+min(3,5)+min(1,5) = 3+3+3+1 = 10 ✓

Example 2 — Larger Batteries

$ Input: n = 2, batteries = [1,1,1,1]

› Output: 2

💡 Note: We can run 2 computers for 2 minutes. Total power needed = 2×2 = 4. Available power = 1+1+1+1 = 4 ✓

Example 3 — Single Computer

$ Input: n = 1, batteries = [1,1,1,1]

› Output: 4

💡 Note: Only 1 computer, so we can use all battery power: 1+1+1+1 = 4 minutes total

Constraints

1 ≤ n ≤ 10⁵
n ≤ batteries.length ≤ 10⁵
1 ≤ batteries[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

n=2 computers, batteries=[3,3,3,1]

Process

Find max time T where total_power ≥ n×T

Output

Maximum runtime = 5 minutes

Key Takeaway

🎯 Key Insight: Use binary search on runtime with greedy power distribution check

Asked in

G Google 35 a Amazon 28 M Microsoft 22 f Meta 18

The key insight is that we need exactly n × T total battery power to run all computers for T minutes. Each battery contributes min(capacity, T) power. Best approach is binary search on answer with greedy feasibility check. Time: O(n log(sum/n)), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer	O(n log(sum/n))	O(1)	Binary search on the answer space with feasibility check
Greedy Optimal Distribution	O(n log(sum/n))	O(1)	Directly calculate optimal runtime using greedy battery distribution
Simulation Approach	O(max(batteries) × n × log n)	O(1)	Try every possible runtime and simulate optimal battery usage

Binary Search on Answer — Algorithm Steps

Step 1: Set search range from 1 to sum of all batteries divided by n
Step 2: For each mid value, check if we can run all computers for mid minutes
Step 3: Use greedy strategy: each battery contributes min(battery_capacity, target_time)

Visualization

Tap to expand

Step-by-Step Walkthrough

Search Space

Runtime between 1 and sum/n

Test Middle

Check if mid runtime is feasible

Narrow Range

Adjust search bounds based on result

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int canRunForTime(int n, int* batteries, int batteriesSize, long long targetTime) {
    long long totalNeeded = (long long)n * targetTime;
    long long totalAvailable = 0;
    
    for (int i = 0; i < batteriesSize; i++) {
        if (batteries[i] < targetTime) {
            totalAvailable += batteries[i];
        } else {
            totalAvailable += targetTime;
        }
        if (totalAvailable >= totalNeeded) {
            return 1;
        }
    }
    
    return totalAvailable >= totalNeeded;
}

long long solution(int n, int* batteries, int batteriesSize) {
    long long sum = 0;
    for (int i = 0; i < batteriesSize; i++) {
        sum += batteries[i];
    }
    
    long long left = 1;
    long long right = sum / n;
    long long result = 0;
    
    while (left <= right) {
        long long mid = (left + right) / 2;
        if (canRunForTime(n, batteries, batteriesSize, mid)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    scanf("%s", line);
    
    int batteries[1000];
    int batteriesSize = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        batteries[batteriesSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%lld\n", solution(n, batteries, batteriesSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log(sum/n))

Binary search has log(sum/n) iterations, each taking O(n) to check feasibility

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra variables for binary search bounds

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

980 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler