# Count Tested Devices After Test Operations
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-tested-devices-after-test-operations)
Canonical: https://scaleengineer.com/dsa/problems/count-tested-devices-after-test-operations
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture)
---
## Problem
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** than `0`:  
  * **Increment** the count of tested devices.
  * **Decrease** the battery percentage of all devices with indices `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)`.
  * 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 <= 100 `
* `0 <= batteryPercentages[i] <= 100`

# Approaches
## Brute-Force Simulation
This approach directly translates the problem description into code. It iterates through each device, and for every device that gets tested, it performs a second iteration over all subsequent devices to update their battery percentages. This is a straightforward simulation of the process.
**Time:** O(n^2), where `n` is the number of devices. The nested loop structure is the cause. In the worst case, the outer loop runs `n` times, and the inner loop can run up to `n-1` times for each outer loop iteration. · **Space:** O(1) extra space. The modifications are done in-place on the input array, and only a constant number of extra variables are used.
**Pros:** Very simple to understand and implement as it directly follows the logic given in the problem statement.
**Cons:** Inefficient due to the O(n^2) time complexity, which can be slow for larger values of `n` (though acceptable for the given constraints).
### Explanation
The brute-force method simulates the test operations exactly as they are described. We use an outer loop to iterate through each device from index `0` to `n-1`. For each device `i`, we check if its current battery percentage is positive. If it is, we count it as a tested device. Then, we trigger an inner loop that runs from `i+1` to `n-1` to decrease the battery percentage of all subsequent devices by 1. We use `Math.max(0, ...)` to ensure the battery percentage never drops below zero. This process continues until all devices have been considered.

```java
class Solution {
    public int countTestedDevices(int[] batteryPercentages) {
        int n = batteryPercentages.length;
        int testedDevices = 0;
        for (int i = 0; i < n; i++) {
            // Check if the current device has enough battery to be tested.
            if (batteryPercentages[i] > 0) {
                testedDevices++;
                // Decrease the battery of all subsequent devices.
                for (int j = i + 1; j < n; j++) {
                    batteryPercentages[j] = Math.max(0, batteryPercentages[j] - 1);
                }
            }
        }
        return testedDevices;
    }
}
```
### Algorithm
- Initialize a counter `testedDevices` to 0.
- Iterate through the `batteryPercentages` array with an index `i` from `0` to `n-1`.
- Inside the loop, check if `batteryPercentages[i]` is greater than `0`.
- If it is, increment `testedDevices`.
- Start a nested loop with an index `j` from `i + 1` to `n-1`.
- In the nested loop, update `batteryPercentages[j]` by taking the maximum of `0` and `batteryPercentages[j] - 1`.
- After the outer loop finishes, return `testedDevices`.

## Optimized Simulation with a Counter
A more efficient approach is to observe that the battery of a device at index `i` is reduced by the number of devices tested before it (i.e., at indices `0` to `i-1`). Instead of updating the entire rest of the array in a nested loop, we can simply keep a running count of the tested devices. This count represents the total reduction that should be applied to the current device's battery percentage.
**Time:** O(n), where `n` is the number of devices. We only need to iterate through the array once. · **Space:** O(1) extra space. We only use a single integer variable to store the count of tested devices.
**Pros:** Highly efficient with a linear time complexity.; Simple implementation with a single loop and one extra variable.; Avoids modifying the input array.
**Cons:** Requires a small logical leap to realize that the explicit updates to the array are unnecessary.
### Explanation
This optimized method avoids the expensive O(n^2) simulation. We realize that for any device `i`, its battery percentage is effectively reduced by the number of successful tests that occurred at indices `j < i`. We can maintain a single variable, say `decrementCount`, to keep track of this number.

We iterate through the `batteryPercentages` array once. For each device `i`, we check if its original battery percentage `batteryPercentages[i]` is greater than the current `decrementCount`. If `batteryPercentages[i] - decrementCount > 0`, it means the device has a positive battery level at the moment of testing. Therefore, we increment our count of tested devices, which is `decrementCount`. This new `decrementCount` will then be used to check the effective battery level for all subsequent devices.

```java
class Solution {
    public int countTestedDevices(int[] batteryPercentages) {
        int decrementCount = 0;
        // The number of tested devices so far also represents the amount
        // by which the battery of subsequent devices has been decreased.
        for (int battery : batteryPercentages) {
            // Check if the current device's battery is greater than the total decrements from previous tests.
            if (battery > decrementCount) {
                // If so, this device gets tested, and we increment the count.
                decrementCount++;
            }
        }
        return decrementCount;
    }
}
```
### Algorithm
- Initialize a counter `decrementCount` to 0. This counter will track the number of devices tested so far.
- Iterate through the `batteryPercentages` array.
- For each device's battery percentage `battery`, calculate its effective battery level after previous tests: `effectiveBattery = battery - decrementCount`.
- If `effectiveBattery > 0`, it means the current device can be tested.
- If the device is tested, increment `decrementCount`.
- After iterating through all the devices, return `decrementCount`.

# Solutions
### Java

```java
class Solution {
public
  int countTestedDevices(int[] batteryPercentages) {
    int ans = 0;
    for (int x : batteryPercentages) {
      x -= ans;
      if (x > 0) {
        ++ans;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countTestedDevices(vector<int> &batteryPercentages) {
    int ans = 0;
    for (int x : batteryPercentages) {
      x -= ans;
      if (x > 0) {
        ++ans;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countTestedDevices(self, batteryPercentages: List[int]) -> int: ans = 0 for x in batteryPercentages: x -= ans ans += x > 0 return ans

```