Count Tested Devices After Test Operations

Count Tested Devices After Test Operations - 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.

Input & Output

Example 1 — Basic Testing Sequence

$ Input: batteryPercentages = [1,1,2,1,3]

› Output: 3

💡 Note: Device 0: battery=1>0, test it (count=1), drain others → [1,0,1,0,2]. Device 1: battery=0, skip. Device 2: battery=1>0, test it (count=2), drain others → [1,0,1,0,1]. Device 3: battery=0, skip. Device 4: battery=1>0, test it (count=3). Total tested = 3.

Example 2 — All Zeros

$ Input: batteryPercentages = [0,0,0]

› Output: 0

💡 Note: All devices start with 0 battery, so none can be tested. Return 0.

Example 3 — Single Device

$ Input: batteryPercentages = [5]

› Output: 1

💡 Note: Only one device with battery=5>0, test it. No other devices to drain. Return 1.

Constraints

1 ≤ batteryPercentages.length ≤ 100
0 ≤ batteryPercentages[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Array of battery percentages: [1,1,2,1,3]

Process

Test devices in order, each test drains future devices by 1

Output

Count of successfully tested devices: 3

Key Takeaway

🎯 Key Insight: Track cumulative drain instead of updating all devices for O(n) efficiency

Asked in

A Amazon 15 M Microsoft 8

The key insight is that each test operation drains all future devices by 1. We can optimize by tracking cumulative drain instead of updating all devices. Best approach uses cumulative drain optimization with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Direct Simulation	O(n²)	O(1)	Simulate the testing process exactly as described
Cumulative Drain Optimization	O(n)	O(1)	Track cumulative battery drain instead of updating all devices

Direct Simulation — Algorithm Steps

Iterate through each device from 0 to n-1
If current device has battery > 0, increment test count and decrease all future devices by 1
Continue to next device
Return total count of tested devices

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Device

Check if current device has battery > 0

Test & Drain

If yes, test it and drain all future devices by 1

Continue

Move to next device and repeat

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* batteryPercentages, int n) {
    int tested = 0;
    
    for (int i = 0; i < n; i++) {
        if (batteryPercentages[i] > 0) {
            tested++;
            // Decrease battery of all devices after current one
            for (int j = i + 1; j < n; j++) {
                if (batteryPercentages[j] > 0) {
                    batteryPercentages[j]--;
                }
            }
        }
    }
    
    return tested;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int batteryPercentages[100];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int val = atoi(token);
        if (val != 0 || token[0] == '0') {
            batteryPercentages[n++] = val;
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(batteryPercentages, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each device (n iterations), we potentially update all remaining devices (n operations)

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for counters, modifying input array in place

✓ Linear Space

12.0K Views

Medium Frequency

~15 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Direct Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler