Scale Engineer

Count Tested Devices After Test Operations

Easy
#2640Time: O(n^2), where `n` is the number of devices. The nested loop structure is the cause. In the worst case, the outer loop runs `n` times, and the inner loop can run up to `n-1` times for each outer loop iteration.Space: O(1) extra space. The modifications are done in-place on the input array, and only a constant number of extra variables are used.1 company
Patterns
Counting
Data structures
Array
Companies
Accenture

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem description into code. It iterates through each device, and for every device that gets tested, it performs a second iteration over all subsequent devices to update their battery percentages. This is a straightforward simulation of the process.

Algorithm

  • Initialize a counter testedDevices to 0.
  • Iterate through the batteryPercentages array with an index i from 0 to n-1.
  • Inside the loop, check if batteryPercentages[i] is greater than 0.
  • If it is, increment testedDevices.
  • Start a nested loop with an index j from i + 1 to n-1.
  • In the nested loop, update batteryPercentages[j] by taking the maximum of 0 and batteryPercentages[j] - 1.
  • After the outer loop finishes, return testedDevices.

Walkthrough

The brute-force method simulates the test operations exactly as they are described. We use an outer loop to iterate through each device from index 0 to n-1. For each device i, we check if its current battery percentage is positive. If it is, we count it as a tested device. Then, we trigger an inner loop that runs from i+1 to n-1 to decrease the battery percentage of all subsequent devices by 1. We use Math.max(0, ...) to ensure the battery percentage never drops below zero. This process continues until all devices have been considered.

class Solution {    public int countTestedDevices(int[] batteryPercentages) {        int n = batteryPercentages.length;        int testedDevices = 0;        for (int i = 0; i < n; i++) {            // Check if the current device has enough battery to be tested.            if (batteryPercentages[i] > 0) {                testedDevices++;                // Decrease the battery of all subsequent devices.                for (int j = i + 1; j < n; j++) {                    batteryPercentages[j] = Math.max(0, batteryPercentages[j] - 1);                }            }        }        return testedDevices;    }}

Complexity

Time

O(n^2), where `n` is the number of devices. The nested loop structure is the cause. In the worst case, the outer loop runs `n` times, and the inner loop can run up to `n-1` times for each outer loop iteration.

Space

O(1) extra space. The modifications are done in-place on the input array, and only a constant number of extra variables are used.

Trade-offs

Pros

  • Very simple to understand and implement as it directly follows the logic given in the problem statement.

Cons

  • Inefficient due to the O(n^2) time complexity, which can be slow for larger values of n (though acceptable for the given constraints).

Solutions

class Solution {public  int countTestedDevices(int[] batteryPercentages) {    int ans = 0;    for (int x : batteryPercentages) {      x -= ans;      if (x > 0) {        ++ans;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem