You are given a 0-indexed integer array batteryPercentages having length n, denoting the battery percentages of n 0-indexed devices.
Your task is to test each device i in order from 0 to n - 1, by performing the following test operations:
batteryPercentages[i] is greater than 0:
j in the range [i + 1, n - 1] by 1, ensuring their battery percentage never goes below 0, i.e, batteryPercentages[j] = max(0, batteryPercentages[j] - 1).Return an integer denoting the number of devices that will be tested after performing the test operations in order.
Example 1:
Input: batteryPercentages = [1,1,2,1,3] Output: 3 Explanation: Performing the test operations in order starting from device 0: At device 0, batteryPercentages[0] > 0, so there is now 1 tested device, and batteryPercentages becomes [1,0,1,0,2]. At device 1, batteryPercentages[1] == 0, so we move to the next device without testing. At device 2, batteryPercentages[2] > 0, so there are now 2 tested devices, and batteryPercentages becomes [1,0,1,0,1]. At device 3, batteryPercentages[3] == 0, so we move to the next device without testing. At device 4, batteryPercentages[4] > 0, so there are now 3 tested devices, and batteryPercentages stays the same. So, the answer is 3.
Example 2:
Input: batteryPercentages = [0,1,2] Output: 2 Explanation: Performing the test operations in order starting from device 0: At device 0, batteryPercentages[0] == 0, so we move to the next device without testing. At device 1, batteryPercentages[1] > 0, so there is now 1 tested device, and batteryPercentages becomes [0,1,1]. At device 2, batteryPercentages[2] > 0, so there are now 2 tested devices, and batteryPercentages stays the same. So, the answer is 2.
Constraints:
1 <= n == batteryPercentages.length <= 100 0 <= batteryPercentages[i] <= 100Problem Overview: You receive an integer array devices where each value represents the battery percentage of a device. Devices are tested from left to right. When you test a device with battery greater than 0, it counts as tested and every device to its right loses 1 battery. The goal is to return how many devices can actually be tested.
Approach 1: Simple Iterative Simulation (O(n²) time, O(1) space)
This method directly simulates the process described in the problem. Iterate through the array from left to right. If devices[i] > 0, increment the tested counter and then iterate through all remaining devices j > i, decrementing each battery value by 1 (while ensuring values don’t go below zero). This approach mirrors the real operations performed during testing, making it easy to reason about.
The downside is the nested iteration. Each successful test triggers another loop over the remaining elements, leading to O(n²) time in the worst case. Space usage stays constant since the array is modified in place. This approach is useful when first understanding the mechanics of the problem or when implementing a straightforward simulation.
Approach 2: Optimized Single-pass Counting (O(n) time, O(1) space)
The key observation is that every successful test reduces the battery of all remaining devices by exactly 1. Instead of actually modifying the rest of the array, track how many tests have already occurred. Let tested represent the number of devices successfully tested so far.
While iterating through the array, compute the effective battery of the current device as devices[i] - tested. If this value is still greater than 0, the device can be tested and you increment tested. Otherwise, the device’s battery would have already dropped to zero due to previous operations.
This removes the need for inner loops or array updates. Each device is processed exactly once, giving O(n) time complexity and O(1) extra space. The technique is essentially a counting optimization built on top of the original array traversal and works because the battery reductions are uniform across all remaining elements. Conceptually, it converts a physical simulation into a simple counting problem.
Recommended for interviews: Start by explaining the simulation approach to demonstrate understanding of the testing process. Then derive the optimized single-pass solution by recognizing that each successful test applies the same decrement to all future elements. Interviewers typically expect the O(n) counting solution since it eliminates unnecessary work while keeping the implementation clean and constant-space.
In this approach, we iterate through the batteryPercentages array from index 0 to n-1. For each element, check if it is greater than 0. If so, increment the count of tested devices and reduce the battery percentage of each following device by 1, ensuring it doesn't go below 0. Continue this process for each device.
This C function iterates over the input array and checks if the current device's battery is greater than 0. If so, it increments the tested devices counter and decreases the battery percentage of all subsequent devices down to a minimum of 0.
Time Complexity: O(n^2), because for each device, you potentially iterate over the rest of the array.
Space Complexity: O(1), as we do not use any additional space except for variables.
This approach avoids redundant computations by keeping a running total of battery power drain and applying it when necessary. Iterate through the list once, applying accumulated drains as soon as a device becomes non-testable.
For each device with a non-zero battery percentage, increment the counter and record a net decrement for future elements instead of re-iterating.
We apply a single loop with a carry forward principle. The `drain` value builds up as you move through the devices, decreasing all subsequent device batteries in a single step.
Time Complexity: O(n), as each element is processed once.
Space Complexity: O(1), because there is no extra memory allocation apart from simple counters.
Assume that the current number of devices we have tested is ans. When testing a new device i, its remaining battery is max(0, batteryPercentages[i] - ans). If the remaining battery is greater than 0, it means this device can be tested, and we need to increase ans by 1.
Finally, return ans.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Simple Iterative Approach | Time Complexity: O(n^2), because for each device, you potentially iterate over the rest of the array. |
| Optimized Single-pass Approach | Time Complexity: O(n), as each element is processed once. |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Iterative Simulation | O(n²) | O(1) | Good for understanding the exact operations described in the problem statement |
| Optimized Single-pass Counting | O(n) | O(1) | Preferred for interviews and production due to linear time and no extra memory |
LeetCode#2960 Count Tested Devices After Test Operations - Python • CodeJulian • 1,242 views views
Watch 9 more video solutions →Practice Count Tested Devices After Test Operations with our built-in code editor and test cases.
Practice on FleetCode