Count Tested Devices After Test Operations

Difficulty: Easy | Acceptance: 78.90% | Paid: No Topics: Array, Simulation, Counting

You are given a 0-indexed integer array batteryPercentages having length n, where batteryPercentages[i] denotes the battery percentage of the ith device.

You are asked to test each device i in order from 0 to n - 1:

• If batteryPercentages[i] is greater than 0:
  • It has been tested.
  • Decrease the battery percentage of all devices with index j (where i < j < n) by 1.

Return an integer denoting the number of devices that have been tested after performing the test operations.

• Examples
• Constraints
• Approach 1: Simulation
• Approach 2: Optimized One-Pass

Examples

Example 1:

Input: batteryPercentages = [1,1,2,1,3]
Output: 3
Explanation: 
- Device 0 is tested because batteryPercentages[0] > 0. batteryPercentages becomes [1,0,1,0,2].
- Device 1 is not tested.
- Device 2 is tested because batteryPercentages[2] > 0. batteryPercentages becomes [1,0,1,0,1].
- Device 3 is not tested.
- Device 4 is tested because batteryPercentages[4] > 0. batteryPercentages becomes [1,0,1,0,0].
There are 3 devices tested.

Example 2:

Input: batteryPercentages = [0,1,2]
Output: 2
Explanation: 
- Device 0 is not tested.
- Device 1 is tested because batteryPercentages[1] > 0. batteryPercentages becomes [0,1,1].
- Device 2 is tested because batteryPercentages[2] > 0. batteryPercentages becomes [0,1,0].
There are 2 devices tested.

Constraints

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

Approach 1: Simulation

Intuition We can directly simulate the process described in the problem statement. We iterate through the array, and whenever we find a device with battery percentage greater than 0, we increment our count and decrement the battery percentage of all subsequent devices by 1.

Steps

• Initialize a counter count to 0.
• Iterate through the array batteryPercentages with index i.
• If batteryPercentages[i] > 0:
  • Increment count.
  • Iterate through the array from index i + 1 to the end, decrementing each element by 1.
• Return count.

from typing import List

class Solution:
    def countTestedDevices(self, batteryPercentages: List[int]) -> int:
        n = len(batteryPercentages)
        count = 0
        for i in range(n):
            if batteryPercentages[i] > 0:
                count += 1
                for j in range(i + 1, n):
                    batteryPercentages[j] -= 1
        return count

Complexity

• Time: O(n²) - In the worst case, for every device, we iterate through the rest of the array.
• Space: O(1) - We modify the array in place and use a constant amount of extra space.
• Notes: This approach is straightforward but not the most efficient for large arrays.

Approach 2: Optimized One-Pass

Intuition Instead of actually modifying the array elements, we can observe that the value of batteryPercentages[i] is effectively reduced by the number of devices tested before it. If we keep track of how many devices have been tested so far (decrement), we can determine if the current device is testable by checking if batteryPercentages[i] - decrement > 0.

Steps

• Initialize count and decrement to 0.
• Iterate through each val in batteryPercentages.
• If val - decrement > 0:
  • Increment count.
  • Increment decrement (since this device will decrement all subsequent devices).
• Return count.

from typing import List

class Solution:
    def countTestedDevices(self, batteryPercentages: List[int]) -> int:
        count = 0
        decrement = 0
        for val in batteryPercentages:
            if val - decrement > 0:
                count += 1
                decrement += 1
        return count

Complexity

• Time: O(n) - We traverse the array exactly once.
• Space: O(1) - We only use two integer variables for tracking.
• Notes: This is the optimal solution, avoiding the nested loop of the simulation approach.