FastPrep
Problem · Array

Count Fully Used Batteries

Learn this problem
● MediumMeta logoMetaINTERNOA
See Meta hiring insights

Problem statement

Your mobile phone is out of power, but you need to keep it working continuously for t minutes. You have several spare batteries, and all of them are fully charged at time 0.

Battery i can power the phone for capacity[i] minutes. Once it is fully depleted, it must recharge for recharge[i] minutes before it can be used again.

Use the batteries in their given cyclic order. When the current battery is fully depleted, move to the next battery. If that battery is still recharging, skip it and continue checking the following batteries in order. If every battery is recharging when the phone needs another battery, the phone cannot remain on continuously.

Return the number of complete battery usages during the required t minutes. A battery counts each time it is fully depleted. If it is impossible to keep the phone working continuously for all t minutes, return -1.

A solution with time complexity no worse than O(t * capacity.length) will fit within the execution time limit.

Function

solution(t: int, capacity: int[], recharge: int[]) → int

Examples

Example 1

t = 16capacity = [2,5,6]recharge = [12,1,4]return = 3
  • Battery 0 powers the phone from time 0 to time 2. It is then depleted, counts as one complete usage, and will be ready again at time 14.
  • Battery 1 runs from time 2 to time 7, counts as the second complete usage, and will be ready again at time 8.
  • Battery 2 runs from time 7 to time 13, counts as the third complete usage, and will be ready again at time 17.
  • At time 13, battery 0 is still recharging, so it is skipped. Battery 1 is ready and supplies the remaining 3 minutes. Because this final use does not fully deplete battery 1, it is not counted.

The phone remains on for all 16 minutes, and the number of complete battery usages is 3.

More Meta problems

drafts saved locally
public int solution(int t, int[] capacity, int[] recharge) {
    // write your code here
}
t16
capacity[2,5,6]
recharge[12,1,4]
expected3
checking account