Count Tested Devices After Test Operations - Solution & Explanation
Problem Statement
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:
- If
batteryPercentages[i]is greater than0:- Increment the count of tested devices.
- Decrease the battery percentage of all devices with indices
jin the range[i + 1, n - 1]by1, ensuring their battery percentage never goes below0, i.e,batteryPercentages[j] = max(0, batteryPercentages[j] - 1). - Move to the next device.
- Otherwise, move to the next device without performing any test.
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 <= 1000 <= batteryPercentages[i] <= 100
Approach Overview
Problem 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.
Approach 1: Simple Iterative Approach
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.
Complexity
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.
Approach 2: Optimized Single-pass Approach
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.
Complexity
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.
Approach 3: Simulation
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).
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
2960. Count Tested Devices After Test Operations || Weekly Leetcode Contest || Solution Explain • CodeLuv • 255 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Tested Devices After Test Operations easy or hard?
Count Tested Devices After Test Operations Python/Java solution
How to solve Count Tested Devices After Test Operations in O(n)?
What is the best approach for Count Tested Devices After Test Operations?
Is Count Tested Devices After Test Operations asked at Google/Amazon/Meta?
What data structure is used in Count Tested Devices After Test Operations?
What is the time complexity of Count Tested Devices After Test Operations?
Ready to solve this problem?
Practice Count Tested Devices After Test Operations with our built-in code editor and test cases.
Practice on FleetCode