Count Tested Devices After Test Operations — Solution
Count Tested Devices After Test Operations solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Count Tested Devices After Test Operations is an easy coding problem on arrays, simulation and counting, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Simulation, Counting
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You test n devices in order, 0 to n - 1. At device i:
- If
batteryPercentages[i] > 0, count it as tested and decrease by 1 the battery of every device after it, never going below 0. - Otherwise skip it.
Return the number of devices tested.
Example 1
Input: batteryPercentages = [1,1,2,1,3]
Output: 3
Explanation: Devices 0, 2 and 4 are tested.
Example 2
Input: batteryPercentages = [0,1,2]
Output: 2
Example 3
Input: batteryPercentages = [0,0,0]
Output: 0
Constraints
1 <= batteryPercentages.length <= 1000 <= batteryPercentages[i] <= 100
Hints for Count Tested Devices After Test Operations
Hint 1
Simulating every decrement is O(n²) — fine here, but there is a one-pass version.
Hint 2
The total decrement applied to device
iis exactly the number of devices tested before it.Hint 3
So device
iis testable whenbatteryPercentages[i] - tested > 0.
How to solve Count Tested Devices After Test Operations
Rather than writing the decrements, carry their count. Device i has already lost one point for each earlier tested device, so its effective battery is battery[i] - tested.
Approach
- Keep
tested, the number of devices tested so far. - At each device, test it when
battery[i] - tested > 0, and incrementtested. - Return
tested.
Why it works
Every tested device decrements all later devices by exactly 1, so the accumulated decrement at position i equals the count of tested devices before i. The floor at 0 never matters: once the effective value hits 0 the device is skipped anyway.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Actually mutating the array works but must clamp at 0 and is quadratic.
- Using
>= 0instead of> 0tests devices whose battery is flat.
Reference solution
Python
from typing import List
def countTestedDevices(batteryPercentages: List[int]) -> int:
tested = 0
for b in batteryPercentages:
if b - tested > 0:
tested += 1
return testedJava
public static int countTestedDevices(int[] batteryPercentages) {
int tested = 0;
for (int b : batteryPercentages) {
if (b - tested > 0) tested++;
}
return tested;
}C++
int countTestedDevices(vector<int>& batteryPercentages) {
int tested = 0;
for (int b : batteryPercentages) {
if (b - tested > 0) tested++;
}
return tested;
}JavaScript
var countTestedDevices = function(batteryPercentages) {
let tested = 0;
for (let i = 0; i < batteryPercentages.length; i++) {
if (batteryPercentages[i] - tested > 0) tested++;
}
return tested;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays