Problem Description

You have n computers and an array of batteries. Each battery has a certain capacity - the i-th battery can power a computer for batteries[i] minutes.

Your goal is to run all n computers simultaneously for as long as possible. Here are the rules:

• Initially, you can insert at most one battery into each computer
• At any point in time, you can swap batteries between computers instantly (removing and inserting takes no time)
• Each battery can only power one computer at a time
• Batteries cannot be recharged - once their power is used, it's gone
• You want all n computers running at the same time

The problem asks you to find the maximum number of minutes that all n computers can run simultaneously.

For example, if you have 2 computers and batteries with capacities [3, 3, 3] minutes, you could:

• Start with 2 batteries in the 2 computers (each with 3 minutes)
• When those are depleted after 3 minutes, swap in the third battery to one computer
• But since you need both computers running simultaneously, the maximum runtime would be 4 minutes total (you can strategically swap batteries to distribute the 9 total minutes across 2 computers)

The key insight is that you can freely swap batteries to optimize the runtime, as long as each computer has a battery at any given moment during the simultaneous operation period.

Intuition

Let's think about what happens when we try to run all n computers for t minutes. The key observation is that if we can run all computers for t minutes, we can definitely run them for any time less than t minutes. This monotonic property suggests binary search might work.

Now, how do we check if it's possible to run all computers for t minutes? Consider what happens with each battery:

• If a battery has capacity greater than t minutes, we can only use t minutes from it (since we're only running for t minutes total)
• If a battery has capacity less than or equal to t minutes, we can use all of it

Since we can swap batteries freely and instantly, the problem becomes: can we distribute the available battery power to keep n computers running for t minutes?

For n computers running t minutes each, we need a total of n * t minutes of battery power. We can get at most min(battery[i], t) minutes from each battery. So the condition becomes:

sum(min(battery[i], t) for all batteries) >= n * t

This gives us a clear way to check feasibility for any given time t.

The binary search approach emerges naturally:

• Search space: from 0 to sum(all batteries) (maximum possible if we had just 1 computer)
• For each candidate time mid, check if we have enough total usable battery power
• If yes, we can potentially run longer, so search the right half
• If no, we need to reduce the time, so search the left half

The beauty of this solution is that it transforms a complex scheduling problem into a simple arithmetic check by recognizing that with free swapping, only the total usable power matters, not the specific assignment of batteries to computers.

Learn more about Greedy, Binary Search and Sorting patterns.

Solution Approach

We implement the solution using binary search on the answer space. Here's how the algorithm works:

Binary Search Setup:

• Initialize left boundary l = 0 (minimum possible runtime)
• Initialize right boundary r = sum(batteries) (maximum theoretical runtime if we had only 1 computer)

Binary Search Loop: While l < r:

1. Calculate the middle point: mid = (l + r + 1) >> 1

   • The >> 1 is a bitwise right shift, equivalent to integer division by 2
   • We use (l + r + 1) instead of (l + r) to avoid infinite loops when l and r are adjacent

2. Feasibility Check:

   • For each battery, calculate how much power we can use if running for mid minutes: min(battery[i], mid)
   • Sum up all usable battery power: sum(min(x, mid) for x in batteries)
   • Check if total usable power is enough: >= n * mid

3. Search Space Adjustment:

   • If feasible (we have enough power for mid minutes):
     • Update l = mid (try for longer runtime)
   • If not feasible:
     • Update r = mid - 1 (reduce the runtime)

Why This Works:

The key insight is that when checking if we can run for mid minutes:

• Batteries with capacity > mid can only contribute mid minutes (capped by runtime)
• Batteries with capacity ≤ mid contribute their full capacity

By summing min(battery[i], mid) for all batteries, we get the total usable battery minutes. If this sum is at least n * mid, we have enough power to keep all n computers running for mid minutes through strategic battery swapping.

Time Complexity: O(m * log(S)) where m is the number of batteries and S is the sum of all battery capacities.

Space Complexity: O(1) as we only use a few variables for the binary search.

The algorithm converges when l equals r, which represents the maximum number of minutes all computers can run simultaneously.

Example Walkthrough

Let's walk through an example with n = 2 computers and batteries = [3, 3, 3].

Step 1: Initialize Binary Search Boundaries

• Left boundary: l = 0 (minimum runtime)
• Right boundary: r = 3 + 3 + 3 = 9 (total battery capacity)

Step 2: First Iteration

• Calculate middle: mid = (0 + 9 + 1) / 2 = 5
• Check if we can run for 5 minutes:
  • Battery 1: min(3, 5) = 3 minutes usable
  • Battery 2: min(3, 5) = 3 minutes usable
  • Battery 3: min(3, 5) = 3 minutes usable
  • Total usable: 3 + 3 + 3 = 9 minutes
  • Need for 2 computers: 2 × 5 = 10 minutes
  • Since 9 < 10, we cannot run for 5 minutes
• Update: r = 5 - 1 = 4

Step 3: Second Iteration

• Calculate middle: mid = (0 + 4 + 1) / 2 = 2
• Check if we can run for 2 minutes:
  • Each battery: min(3, 2) = 2 minutes usable
  • Total usable: 2 + 2 + 2 = 6 minutes
  • Need for 2 computers: 2 × 2 = 4 minutes
  • Since 6 ≥ 4, we can run for 2 minutes
• Update: l = 2

Step 4: Third Iteration

• Calculate middle: mid = (2 + 4 + 1) / 2 = 3
• Check if we can run for 3 minutes:
  • Each battery: min(3, 3) = 3 minutes usable
  • Total usable: 3 + 3 + 3 = 9 minutes
  • Need for 2 computers: 2 × 3 = 6 minutes
  • Since 9 ≥ 6, we can run for 3 minutes
• Update: l = 3

Step 5: Fourth Iteration

• Calculate middle: mid = (3 + 4 + 1) / 2 = 4
• Check if we can run for 4 minutes:
  • Each battery: min(3, 4) = 3 minutes usable
  • Total usable: 3 + 3 + 3 = 9 minutes
  • Need for 2 computers: 2 × 4 = 8 minutes
  • Since 9 ≥ 8, we can run for 4 minutes
• Update: l = 4

Step 6: Termination

• Now l = 4 and r = 4, so the loop ends
• The answer is 4 minutes

This makes sense: With 9 total battery minutes and 2 computers, we can theoretically achieve 4.5 minutes per computer, but since we need whole minutes and must keep both running simultaneously, the maximum is 4 minutes.

Solution Implementation

Time and Space Complexity

The time complexity is O(m × log S), where m is the number of batteries (length of the batteries list) and S is the sum of all battery powers.

The binary search runs for O(log S) iterations since we're searching in the range [0, sum(batteries)]. In each iteration of the binary search, we compute sum(min(x, mid) for x in batteries), which iterates through all m batteries, taking O(m) time. Therefore, the overall time complexity is O(m × log S).

The space complexity is O(1) as we only use a constant amount of extra space for variables l, r, and mid. The generator expression sum(min(x, mid) for x in batteries) doesn't create an intermediate list but computes the sum on-the-fly, using constant extra space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in Binary Search Boundary

Pitfall: Setting the right boundary as sum(batteries) can cause integer overflow in languages with fixed integer sizes when battery capacities are large.

Solution: In Python, this isn't an issue due to arbitrary precision integers, but in languages like Java or C++, use long type or cap the right boundary at sum(batteries) // n since that's the theoretical maximum anyway.

2. Incorrect Binary Search Middle Calculation

Pitfall: Using mid = (left + right) // 2 instead of mid = (left + right + 1) // 2 can cause an infinite loop when left = right - 1 and the condition at mid is satisfied.

Example scenario:

• If left = 3, right = 4 and mid = 3 satisfies the condition
• We set left = mid = 3, keeping us in the same state forever

Solution: Always use mid = (left + right + 1) // 2 when updating left = mid in the binary search to ensure progress.

3. Misunderstanding the Feasibility Check Logic

Pitfall: Thinking that batteries must be assigned to specific computers or that we need to simulate the actual battery swapping process.

Incorrect approach:

# Wrong: Trying to assign batteries to computers
if len(batteries) >= n and all(b >= mid for b in batteries[:n]):
    # This doesn't account for battery swapping optimization

Solution: The correct approach uses the greedy insight that we can pool all available battery minutes (capped at mid) and check if the total is sufficient for n * mid minutes of runtime.

4. Off-by-One Error in Binary Search

Pitfall: Using while left <= right with this update pattern can cause the algorithm to miss the correct answer or get stuck.

Solution: Stick to while left < right with the update pattern of left = mid and right = mid - 1 to ensure convergence at the correct answer.

5. Not Capping Battery Contribution

Pitfall: Forgetting to use min(battery_capacity, mid) and instead using the full battery capacity when checking feasibility.

Incorrect:

total_contribution = sum(batteries)  # Wrong!
if total_contribution >= n * mid:
    ...

Solution: Each battery can only contribute up to mid minutes toward the target runtime, regardless of its actual capacity. A 100-minute battery only provides 10 useful minutes if we're checking for a 10-minute runtime.