Watch 10 video solutions for Count Tested Devices After Test Operations, a easy level problem involving Array, Simulation, Counting. This walkthrough by CodeJulian has 1,242 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |