Problem Description

You have an array batteryPercentages representing the battery levels of n devices indexed from 0 to n-1. You need to test these devices in order from index 0 to n-1.

The testing process works as follows:

For each device i:

• If batteryPercentages[i] > 0:
  • The device gets tested (increment your count of tested devices)
  • All devices after this one (indices i+1 to n-1) lose 1% battery
  • Battery percentages cannot go below 0, so use max(0, batteryPercentages[j] - 1)
  • Move to the next device
• If batteryPercentages[i] = 0:
  • Skip testing this device
  • Move to the next device

Return the total number of devices that get tested.

Key insight from the solution: When we reach device i, if we've already tested ans devices, then device i has already lost ans percent battery (1% for each previously tested device). So its actual battery level is max(0, batteryPercentages[i] - ans). The device can be tested if this value is greater than 0, which simplifies to checking if batteryPercentages[i] > ans.

This is why the elegant solution simply checks x > ans for each battery percentage x and increments ans when true.

Intuition

Let's trace through what happens when we test devices. When we test the first device (if its battery > 0), all subsequent devices lose 1% battery. When we test the second device, all devices after it lose another 1% battery. We can observe a pattern here.

By the time we reach device i, how much battery has it lost? It has lost 1% for each device that was tested before it. If we've tested ans devices so far, then device i has lost exactly ans percent battery.

So when evaluating whether device i can be tested, we need to check if its remaining battery is positive:

• Original battery: batteryPercentages[i]
• Battery lost: ans (number of previously tested devices)
• Remaining battery: batteryPercentages[i] - ans

Device i can be tested if batteryPercentages[i] - ans > 0, which simplifies to batteryPercentages[i] > ans.

This realization transforms the problem from simulating battery decreases (which would require updating all future devices each time we test one) into a simple comparison. We just need to track how many devices we've tested (ans) and for each device, check if its original battery percentage exceeds this count.

The beauty of this approach is that we don't need to actually modify the array or keep track of current battery levels. The original battery percentage tells us everything we need to know when combined with the count of previously tested devices.

Solution Approach

The solution uses a simple linear scan with a counter variable. Here's how it works:

1. Initialize a counter: Start with ans = 0 to track the number of tested devices.

2. Iterate through each device: For each battery percentage x in the array:

   • Check if x > ans
   • If true, it means this device can be tested (its original battery minus the number of previously tested devices is still positive)
   • When a device can be tested, increment ans by 1 using the expression ans += x > ans (this adds 1 if the condition is true, 0 if false)

3. Return the result: After checking all devices, ans contains the total number of tested devices.

Why this works:

• When we're at device i, exactly ans devices have been tested before it
• Each tested device reduces the battery of all subsequent devices by 1
• So device i's effective battery is max(0, batteryPercentages[i] - ans)
• The device can be tested if this value is greater than 0
• This simplifies to checking if batteryPercentages[i] > ans

Time Complexity: O(n) where n is the length of the array, as we make a single pass through all devices.

Space Complexity: O(1) as we only use a constant amount of extra space for the counter variable.

The elegance of this solution lies in avoiding the simulation of battery decreases entirely, replacing it with a simple mathematical observation about the relationship between original battery percentages and the number of previously tested devices.

Example Walkthrough

Let's walk through the solution with batteryPercentages = [1, 1, 2, 1, 3].

We'll track ans (number of tested devices) and check each device:

Device 0 (battery = 1):

• Check: Is 1 > ans (1 > 0)? Yes!
• Test this device: ans = 1
• Note: All subsequent devices conceptually lose 1% battery

Device 1 (battery = 1):

• Check: Is 1 > ans (1 > 1)? No!
• Skip this device: ans remains 1
• Why? This device has already lost 1% from testing device 0, so its effective battery is 1 - 1 = 0

Device 2 (battery = 2):

• Check: Is 2 > ans (2 > 1)? Yes!
• Test this device: ans = 2
• This device started with 2%, lost 1% from device 0, has 1% remaining - enough to test

Device 3 (battery = 1):

• Check: Is 1 > ans (1 > 2)? No!
• Skip this device: ans remains 2
• This device has lost 2% total (from devices 0 and 2), so effective battery is 1 - 2 = -1 (capped at 0)

Device 4 (battery = 3):

• Check: Is 3 > ans (3 > 2)? Yes!
• Test this device: ans = 3
• Started with 3%, lost 2% from previous tests, has 1% remaining - can test

Result: 3 devices tested (devices at indices 0, 2, and 4)

The key insight: Instead of simulating battery drain on all devices, we just check if each device's original battery exceeds the count of previously tested devices. This works because a device at position i will have lost exactly ans percent battery by the time we reach it.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the batteryPercentages array. The algorithm iterates through the array exactly once, performing a constant-time comparison operation (x > ans) for each element.

The space complexity is O(1). The algorithm only uses a single variable ans to keep track of the count, regardless of the input size. No additional data structures that grow with the input are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Attempting to Simulate Battery Drainage

The Mistake: Many developers initially try to actually modify the array by decreasing battery percentages after each test:

# Incorrect approach - unnecessarily complex and inefficient
def countTestedDevices(self, batteryPercentages: List[int]) -> int:
    tested_count = 0
    n = len(batteryPercentages)
  
    for i in range(n):
        if batteryPercentages[i] > 0:
            tested_count += 1
            # Actually modifying the array - unnecessary!
            for j in range(i + 1, n):
                batteryPercentages[j] = max(0, batteryPercentages[j] - 1)
  
    return tested_count

Why it's wrong: This approach has O(n²) time complexity and modifies the input array unnecessarily. The key insight is that we don't need to simulate the battery drain - we can calculate the effective battery level mathematically.

The Fix: Use the mathematical relationship: when at device i, if tested_count devices have been tested, the effective battery is original_battery - tested_count. Simply check if battery_level > tested_count.

Pitfall 2: Misunderstanding the Battery Drain Timing

The Mistake: Thinking that the current device's battery is affected by its own testing:

# Incorrect - applying drain before checking if device can be tested
def countTestedDevices(self, batteryPercentages: List[int]) -> int:
    tested_count = 0
  
    for battery_level in batteryPercentages:
        # Wrong: subtracting tested_count + 1 instead of tested_count
        if battery_level > tested_count + 1:
            tested_count += 1
  
    return tested_count

Why it's wrong: The battery drain from previously tested devices affects the current device, but the current device doesn't drain its own battery before being tested.

The Fix: The correct condition is battery_level > tested_count, not battery_level > tested_count + 1.

Pitfall 3: Using >= Instead of > in the Comparison

The Mistake: Using greater than or equal to instead of strictly greater than:

# Incorrect - wrong comparison operator
def countTestedDevices(self, batteryPercentages: List[int]) -> int:
    tested_count = 0
  
    for battery_level in batteryPercentages:
        # Wrong: should be > not >=
        if battery_level >= tested_count:
            tested_count += 1
  
    return tested_count

Why it's wrong: A device with effective battery of 0 cannot be tested. If battery_level == tested_count, the effective battery is battery_level - tested_count = 0, so the device cannot be tested.

The Fix: Use strict inequality: battery_level > tested_count.