LeetCode 2960 - Count Tested Devices After Test Operations

LeetCode Problem 2960

Difficulty: 🟢 Easy
Topics: Array, Simulation, Counting

Solution

Problem Understanding

This problem asks us to simulate a sequence of device tests based on battery percentages. We are given a 0-indexed integer array batteryPercentages, where each element represents the current battery level of a device. We process the devices from left to right, starting at index 0 and ending at index n - 1.

For each device, we decide whether it gets tested. A device is tested only if its battery percentage is greater than 0 at the moment we reach it. If a device is tested, we increase our count of tested devices and then reduce the battery percentage of every device to its right by 1. Importantly, no battery percentage can drop below 0.

The challenge comes from the fact that testing one device changes the battery values of future devices. This means a device that initially had a positive battery might later become 0 before we reach it, making it impossible to test.

The input is an integer array where:

• batteryPercentages[i] represents the battery percentage of device i
• The array length n tells us how many devices there are

The output is a single integer representing how many devices are successfully tested after applying all operations in order.

The constraints are relatively small:

• 1 <= n <= 100
• 0 <= batteryPercentages[i] <= 100

These constraints tell us that even a brute-force simulation is computationally feasible because the input size is tiny. However, since this is a technical reference document, it is useful to think about whether a cleaner and more efficient approach exists.

An important observation is that every time we successfully test a device, all later devices lose exactly 1 battery. Therefore, instead of explicitly modifying the array every time, we can simply keep track of how many successful tests have happened so far and determine what each device's effective battery would be.

Several edge cases are worth identifying early. Arrays containing only zeros should return 0 because no device can ever be tested. Arrays with very high battery values may allow every device to be tested. A particularly tricky case is when repeated reductions cause future devices to hit exactly 0, because a naive implementation may incorrectly allow negative values or accidentally test a device that should no longer qualify.

Approaches

Brute Force Simulation

The most direct way to solve this problem is to literally simulate the operations exactly as described.

We iterate through the devices from left to right. Whenever we encounter a device with battery greater than 0, we increment our tested device count and then loop through all later devices to reduce their battery percentage by 1, ensuring no value goes below 0.

This approach is correct because it follows the problem statement precisely. Every battery update is explicitly applied, so there is no ambiguity about the state of future devices.

However, the downside is inefficiency. For every tested device, we may need to traverse the remainder of the array to decrease battery percentages. In the worst case, this creates nested iteration.

Optimal Observation-Based Simulation

The key insight is that we do not actually need to modify the array.

Suppose we have already tested k devices. Every future device would have been reduced exactly k times, because each successful test decreases all later devices by 1.

This means that when we reach device i, its effective battery percentage is:

batteryPercentages[i] - testedCount

If this value is still positive, we can test the device and increment the tested count.

Instead of repeatedly updating the entire suffix of the array, we only track how many successful tests have happened so far. This eliminates unnecessary repeated work and simplifies the implementation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Direct simulation by modifying future battery values
Optimal	O(n)	O(1)	Track cumulative reductions instead of modifying the array

Algorithm Walkthrough

The optimal algorithm works by maintaining how many devices have already been tested.

1. Initialize a variable tested_devices to 0. This variable serves two purposes: it counts successful tests and also represents how many times future devices have been reduced.
2. Iterate through each battery percentage in the array from left to right.
3. For the current device, calculate its effective battery level by subtracting tested_devices from the original battery percentage.
4. If the effective battery is still greater than 0, this means the device can be tested. Increment tested_devices.
5. Continue until all devices have been processed.
6. Return tested_devices as the final answer.

The reason this works is that each successful test reduces all future devices exactly once. Instead of explicitly applying those reductions, we represent them implicitly using the running count of tested devices.

Why it works

The invariant is that after testing k devices, every unprocessed device has effectively lost exactly k battery percentage points. Since all reductions are uniform and cumulative, subtracting tested_devices from the current battery value perfectly reproduces the result of the full simulation. Therefore, whenever batteryPercentages[i] - tested_devices > 0, the device is testable in the real process as well.

Python Solution

from typing import List

class Solution:
    def countTestedDevices(self, batteryPercentages: List[int]) -> int:
        tested_devices = 0

        for battery in batteryPercentages:
            if battery - tested_devices > 0:
                tested_devices += 1

        return tested_devices

This implementation follows the optimal algorithm directly.

We begin by initializing tested_devices to 0. This variable tracks how many devices have already been successfully tested.

Next, we iterate through every battery percentage in the array. Instead of mutating future elements, we compute the device's effective battery level using battery - tested_devices.

If this value is positive, the device survives all previous reductions and can still be tested. We increment tested_devices, which automatically accounts for the future reduction effect on subsequent devices.

Finally, after processing all devices, we return the total number of successful tests.

Go Solution

func countTestedDevices(batteryPercentages []int) int {
    testedDevices := 0

    for _, battery := range batteryPercentages {
        if battery-testedDevices > 0 {
            testedDevices++
        }
    }

    return testedDevices
}

The Go implementation is nearly identical to the Python version. Since Go slices naturally handle iteration, we use a range loop to process each battery percentage.

There is no need for special handling of nil versus empty slices because the problem guarantees at least one element. Integer overflow is also not a concern because values remain very small under the given constraints.

The main implementation detail is using Go's := syntax for variable initialization and explicit integer comparisons.

Worked Examples

Example 1

Input:

batteryPercentages = [1,1,2,1,3]

We track only the tested_devices counter.

Index	Original Battery	Tested So Far	Effective Battery	Tested?	New Tested Count
0	1	0	1	Yes	1
1	1	1	0	No	1
2	2	1	1	Yes	2
3	1	2	-1	No	2
4	3	2	1	Yes	3

Final answer:

3

This matches the problem statement's detailed simulation.

Example 2

Input:

batteryPercentages = [0,1,2]

Index	Original Battery	Tested So Far	Effective Battery	Tested?	New Tested Count
0	0	0	0	No	0
1	1	0	1	Yes	1
2	2	1	1	Yes	2

Final answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We scan the array once, performing constant-time work per element
Space	O(1)	Only a few integer variables are used

The algorithm processes each device exactly once and never revisits earlier elements. Since we avoid explicitly updating future battery values, there is no nested iteration. Memory usage stays constant regardless of input size because we only maintain a running counter.

Test Cases

class Solution:
    def countTestedDevices(self, batteryPercentages):
        tested_devices = 0

        for battery in batteryPercentages:
            if battery - tested_devices > 0:
                tested_devices += 1

        return tested_devices

solution = Solution()

assert solution.countTestedDevices([1, 1, 2, 1, 3]) == 3  # Example 1
assert solution.countTestedDevices([0, 1, 2]) == 2  # Example 2

assert solution.countTestedDevices([0]) == 0  # Single device, zero battery
assert solution.countTestedDevices([5]) == 1  # Single device, positive battery

assert solution.countTestedDevices([0, 0, 0, 0]) == 0  # All devices dead
assert solution.countTestedDevices([10, 10, 10]) == 3  # Every device survives reductions

assert solution.countTestedDevices([1, 1, 1, 1]) == 1  # Future reductions eliminate others
assert solution.countTestedDevices([1, 2, 3, 4]) == 2  # Mixed survival after reductions

assert solution.countTestedDevices([100] * 100) == 100  # Maximum battery values
assert solution.countTestedDevices([0] * 100) == 0  # Large all-zero case

Test	Why
[1,1,2,1,3]	Validates Example 1 behavior
[0,1,2]	Validates Example 2 behavior
[0]	Minimum size with no testable device
[5]	Minimum size with testable device
[0,0,0,0]	Ensures all-zero arrays return 0
[10,10,10]	Ensures every device can be tested
[1,1,1,1]	Verifies repeated reductions eliminate future devices
[1,2,3,4]	Tests mixed outcomes
[100] * 100	Stress test with maximum battery values
[0] * 100	Stress test with many non-testable devices

Edge Cases

One important edge case is when all devices start with zero battery, such as [0,0,0]. A buggy implementation might accidentally count devices after reductions or mishandle comparisons. In our solution, every device fails the condition battery - tested_devices > 0, so the result correctly remains 0.

Another important case occurs when a device reaches exactly zero after reductions. For example, in [1,1,1], testing the first device causes the remaining devices to lose 1 battery and become 0. A naive implementation might mistakenly test them if it uses >= 0 instead of > 0. Our implementation correctly requires the effective battery to remain strictly positive.

A third important edge case is when all devices have very large battery values, such as [100,100,100]. Since reductions are relatively small compared to battery size, every device remains testable. Our implementation naturally handles this because each device still has positive effective battery after subtracting the number of tested devices.

Finally, a single-element array deserves attention because it represents the smallest possible input size. If the battery is positive, we return 1; otherwise 0. Since the algorithm simply iterates once, no special handling is needed.