2960. Count Tested Devices After Test Operations

SourceWeekly Contest 375 Q1DifficultyEasyRating1169

Description

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

Solutions

Solution 1: Simulation

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

Finally, return \(\textit{ans}\).

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

1
2
3
4
5
6

class Solution:
    def countTestedDevices(self, batteryPercentages: list[int]) -> int:
        ans = 0
        for x in batteryPercentages:
            ans += x > ans
        return ans

1
2
3
4
5
6
7
8
9

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    int countTestedDevices(vector<int>& batteryPercentages) {
        int ans = 0;
        for (int x : batteryPercentages) {
            ans += x > ans;
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8

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

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7
8
9

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
    }
}

Comments