Maximum Running Time of N Computers

HardBinary Searchbinary search on answer

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You have n identical computers and a list batteries, where batteries[i] is the number of minutes battery i can power a computer. You want all n computers to run **simultaneously** for as long as possible. At the start, place one battery in each computer. At any integer minute you may remove batteries and insert others, any number of times, instantly; batteries do not recharge, and a battery sitting outside a computer does not drain. Each battery can power at most one computer at a time. Return the maximum number of whole minutes all n computers can run together. The answer can exceed the 32-bit range.

Examples

Input: n = 2, batteries = [3,3,3]
Output: 4
Minutes 1-2: batteries 0 and 1. Minute 3: batteries 0 and 2. Minute 4: batteries 1 and 2. Only battery 2 has charge left afterwards, so a 5th minute is impossible.
Input: n = 2, batteries = [1,1,1,1]
Output: 2
Use two batteries for the first minute and the other two for the second.

Constraints

  • 1 <= n <= batteries.length <= 10^5
  • 1 <= batteries[i] <= 10^9

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More binary search on answer problems