2960. Count Tested Devices After Test Operations

The 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

Approach overview

Problem 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 1: Simple Iterative Approach

In this approach, we iterate through the batteryPercentages array from index 0 to n-1. For each element, check if it is greater than 0. If so, increment the count of tested devices and reduce the battery percentage of each following device by 1, ensuring it doesn't go below 0. Continue this process for each device.

Python


def count_tested_devices(battery_percentages):
    tested_devices = 0
    n = len(battery_percentages)
    for i in range(n):
        if battery_percentages[i] > 0:
            tested_devices += 1
            for j in range(i + 1, n):
                battery_percentages[j] = max(0, battery_percentages[j] - 1)
    return tested_devices

battery_percentages = [1, 1, 2, 1, 3]
print(count_tested_devices(battery_percentages))

Java


public class Main {
    public static int countTestedDevices(int[] batteryPercentages) {
        int testedDevices = 0;
        int n = batteryPercentages.length;
        for (int i = 0; i < n; i++) {
            if (batteryPercentages[i] > 0) {
                testedDevices++;
                for (int j = i + 1; j < n; j++) {
                    batteryPercentages[j] = Math.max(0, batteryPercentages[j] - 1);
                }
            }
        }
        return testedDevices;
    }

    public static void main(String[] args) {
        int[] batteryPercentages = {1, 1, 2, 1, 3};
        System.out.print(countTestedDevices(batteryPercentages));
    }
}

C++


#include <iostream>
#include <vector>
using namespace std;

int countTestedDevices(vector<int> &batteryPercentages) {
    int testedDevices = 0;
    int n = batteryPercentages.size();
    for (int i = 0; i < n; i++) {
        if (batteryPercentages[i] > 0) {
            testedDevices++;
            for (int j = i + 1; j < n; j++) {
                batteryPercentages[j] = max(0, batteryPercentages[j] - 1);
            }
        }
    }
    return testedDevices;
}

int main() {
    vector<int> batteryPercentages = {1, 1, 2, 1, 3};
    cout << countTestedDevices(batteryPercentages);
    return 0;
}

JavaScript


function countTestedDevices(batteryPercentages) {
    let testedDevices = 0;
    let n = batteryPercentages.length;
    for (let i = 0; i < n; i++) {
        if (batteryPercentages[i] > 0) {
            testedDevices++;
            for (let j = i + 1; j < n; j++) {
                batteryPercentages[j] = Math.max(0, batteryPercentages[j] - 1);
            }
        }
    }
    return testedDevices;
}

let batteryPercentages = [1, 1, 2, 1, 3];
console.log(countTestedDevices(batteryPercentages));


#include <stdio.h>

int countTestedDevices(int batteryPercentages[], int n) {
    int testedDevices = 0;
    for (int i = 0; i < n; i++) {
        if (batteryPercentages[i] > 0) {
            testedDevices++;
            for (int j = i + 1; j < n; j++) {
                if (batteryPercentages[j] > 0) {
                    batteryPercentages[j]--;
                }
            }
        }
    }
    return testedDevices;
}

int main() {
    int batteryPercentages[] = {1, 1, 2, 1, 3};
    int n = sizeof(batteryPercentages)/sizeof(batteryPercentages[0]);
    printf("%d", countTestedDevices(batteryPercentages, n));
    return 0;
}


using System;

public class Program {
    public static int CountTestedDevices(int[] batteryPercentages) {
        int testedDevices = 0;
        int n = batteryPercentages.Length;
        for (int i = 0; i < n; i++) {
            if (batteryPercentages[i] > 0) {
                testedDevices++;
                for (int j = i + 1; j < n; j++) {
                    batteryPercentages[j] = Math.Max(0, batteryPercentages[j] - 1);
                }
            }
        }
        return testedDevices;
    }

    public static void Main() {
        int[] batteryPercentages = {1, 1, 2, 1, 3};
        Console.WriteLine(CountTestedDevices(batteryPercentages));
    }
}

In Python, we leverage the list's inherent features to iterate and manage battery percentages, with simple loops and conditional checks.

Complexity

Time Complexity: O(n^2), rooted in the nested loop structure.
Space Complexity: O(1) as it works in-place on lists.

Try this approach in the editor

Approach 2: Optimized Single-pass Approach

This approach avoids redundant computations by keeping a running total of battery power drain and applying it when necessary. Iterate through the list once, applying accumulated drains as soon as a device becomes non-testable.

For each device with a non-zero battery percentage, increment the counter and record a net decrement for future elements instead of re-iterating.

Python


def count_tested_devices(battery_percentages):
    tested_devices = 0
    drain = 0
    for battery in battery_percentages:
        if battery > drain:
            tested_devices += 1
            drain += 1
    return tested_devices

battery_percentages = [1, 1, 2, 1, 3]
print(count_tested_devices(battery_percentages))

Java


public class Main {
    public static int countTestedDevices(int[] batteryPercentages) {
        int testedDevices = 0, drain = 0;
        for (int i = 0; i < batteryPercentages.length; i++) {
            if (batteryPercentages[i] - drain > 0) {
                testedDevices++;
                drain++;
            }
        }
        return testedDevices;
    }

    public static void main(String[] args) {
        int[] batteryPercentages = {1, 1, 2, 1, 3};
        System.out.print(countTestedDevices(batteryPercentages));
    }
}

C++


#include <iostream>
#include <vector>
using namespace std;

int countTestedDevices(vector<int> &batteryPercentages) {
    int testedDevices = 0, drain = 0;
    for (int i = 0; i < batteryPercentages.size(); i++) {
        if (batteryPercentages[i] - drain > 0) {
            testedDevices++;
            drain++;
        }
    }
    return testedDevices;
}

int main() {
    vector<int> batteryPercentages = {1, 1, 2, 1, 3};
    cout << countTestedDevices(batteryPercentages);
    return 0;
}

JavaScript


function countTestedDevices(batteryPercentages) {
    let testedDevices = 0;
    let drain = 0;
    for (let battery of batteryPercentages) {
        if (battery > drain) {
            testedDevices++;
            drain++;
        }
    }
    return testedDevices;
}

let batteryPercentages = [1, 1, 2, 1, 3];
console.log(countTestedDevices(batteryPercentages));


#include <stdio.h>

int countTestedDevices(int batteryPercentages[], int n) {
    int testedDevices = 0, drain = 0;
    for (int i = 0; i < n; i++) {
        if (batteryPercentages[i] - drain > 0) {
            testedDevices++;
            drain++;
        }
    }
    return testedDevices;
}

int main() {
    int batteryPercentages[] = {1, 1, 2, 1, 3};
    int n = sizeof(batteryPercentages)/sizeof(batteryPercentages[0]);
    printf("%d", countTestedDevices(batteryPercentages, n));
    return 0;
}


using System;

public class Program {
    public static int CountTestedDevices(int[] batteryPercentages) {
        int testedDevices = 0, drain = 0;
        foreach (int battery in batteryPercentages) {
            if (battery > drain) {
                testedDevices++;
                drain++;
            }
        }
        return testedDevices;
    }

    public static void Main() {
        int[] batteryPercentages = {1, 1, 2, 1, 3};
        Console.WriteLine(CountTestedDevices(batteryPercentages));
    }
}

Python offers a brief but powerful approach by managing a cumulative drain value that modifies future device capabilities in a single scan.

Complexity

Time Complexity: O(n), just a single linear pass.
Space Complexity: O(1), due to in-place updates.

Try this approach in the editor

Approach 3: Simulation

Assume that the current number of devices we have tested is ans. When testing a new device i, its remaining battery is max(0, batteryPercentages[i] - ans). If the remaining battery is greater than 0, it means this device can be tested, and we need to increase ans by 1.

Finally, return ans.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

TypeScript

function countTestedDevices(batteryPercentages: number[]): number {
    let ans = 0;
    for (const x of batteryPercentages) {
        ans += x > ans ? 1 : 0;
    }
    return ans;
}

func countTestedDevices(batteryPercentages []int) (ans int) {
	for _, x := range batteryPercentages {
		if x > ans {
			ans++
		}
	}
	return
}

Rust

impl Solution {
    pub fn count_tested_devices(battery_percentages: Vec<i32>) -> i32 {
        let mut ans = 0;
        for x in battery_percentages {
            ans += if x > ans { 1 } else { 0 };
        }
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Simple Iterative Approach	Time Complexity: O(n^2), rooted in the nested loop structure. Space Complexity: O(1) as it works in-place on lists.
Optimized Single-pass Approach	Time Complexity: O(n), just a single linear pass. Space Complexity: O(1), due to in-place updates.
Simulation	–

Complexity analysis

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

Frequently asked questions

Is Count Tested Devices After Test Operations easy or hard?

Count Tested Devices After Test Operations is classified as an Easy problem on LeetCode. The main challenge is recognizing that repeated battery reductions can be represented by a single counter instead of modifying the array after every test.

Count Tested Devices After Test Operations Python/Java solution

In both Python and Java, the optimal implementation iterates through the devices array and maintains a tested counter. For each element, check if devices[i] - tested > 0 and increment the counter if true. The logic is identical across languages and runs in O(n) time with constant extra space.

How to solve Count Tested Devices After Test Operations in O(n)?

Maintain a variable called tested that counts how many devices have already been tested. Iterate through the array and compute the effective battery as devices[i] - tested. If this value is greater than zero, increment tested. This avoids repeatedly decrementing the remaining elements and keeps the algorithm linear.

What is the best approach for Count Tested Devices After Test Operations?

The optimal approach is a single-pass counting technique. Instead of decreasing the battery of all remaining devices after each test, track how many devices have already been tested and subtract that value from the current device’s battery. If devices[i] - tested > 0, the device can still be tested. This runs in O(n) time and O(1) space.

Is Count Tested Devices After Test Operations asked at Google/Amazon/Meta?

Problems with similar patterns—array traversal with simulation optimization—frequently appear in interviews at companies like Amazon and Google. The exact problem may vary, but recognizing when a simulation can be replaced with a counting or prefix technique is a common interview skill.

What data structure is used in Count Tested Devices After Test Operations?

The problem primarily uses an array for sequential traversal. The optimized solution only adds a simple integer counter to track how many decrements would have been applied to future elements.

What is the time complexity of Count Tested Devices After Test Operations?

The optimal solution runs in O(n) time because the array is scanned once. Each device is evaluated using a simple arithmetic check without modifying the rest of the array. Space complexity is O(1) since only a counter variable is used.

Count Tested Devices After Test Operations solution and explanation

The problem

Approach overview

Approach 1: Simple Iterative Approach

Approach 2: Optimized Single-pass Approach

Approach 3: Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Count Tested Devices After Test Operations solution and explanation

The problem

Approach overview

Approach 1: Simple Iterative Approach

Approach 2: Optimized Single-pass Approach

Approach 3: Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems