2960

2960. Count Tested Devices After Test Operations (Easy)

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:

  <ul>
  	<li><strong>Increment</strong> the count of tested devices.</li>
  	<li><strong>Decrease</strong> the battery percentage of all devices with indices <code>j</code> in the range <code>[i + 1, n - 1]</code> by <code>1</code>, ensuring their battery percentage <strong>never goes below</strong> <code>0</code>, i.e, <code>batteryPercentages[j] = max(0, batteryPercentages[j] - 1)</code>.</li>
  	<li>Move to the next device.</li>
  </ul>
  </li>
  <li>Otherwise, move to the next device without performing any test.</li>
  

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

Hints:

• One solution is simulating the operations as explained in the problem statement, and it works in O(n2) time.
• While going through the devices, you can maintain the number of previously tested devices, and the current device can be tested if batteryPercentages[i] is greater than the number of tested devices.

Solution 1. Brute Force

// OJ: https://leetcode.com/problems/count-tested-devices-after-test-operations/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    int countTestedDevices(vector<int>& A) {
        int ans = 0, N = A.size();
        for (int i = 0; i < N; ++i) {
            if (A[i] == 0) continue;
            ++ans;
            for (int j = i + 1; j < N; ++j) {
                A[j] = max(0, A[j] - 1);
            }
        }
        return ans;
    }
};

Solution 2. One Pass

// OJ: https://leetcode.com/problems/count-tested-devices-after-test-operations/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int countTestedDevices(vector<int>& A) {
        int ans = 0, N = A.size();
        for (int i = 0; i < N; ++i) {
            ans += A[i] - ans > 0;
        }
        return ans;
    }
};

Discussion

https://leetcode.com/problems/count-tested-devices-after-test-operations/solutions/4384483/c-one-pass/