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.

Examples

Example 1

1
2
3
4
5
6
7
8
9

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

1
2
3
4
5
6
7

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

Solution

Method 1 – Simulation (Greedy)

Intuition

We process each device in order. If the battery is greater than 0, we count it as tested and decrease the battery of all subsequent devices by 1 (not going below 0). This simulates the process as described.

Approach

  1. Iterate through the array from left to right.
  2. For each device, if its battery is greater than 0:
    • Increment the answer.
    • For all subsequent devices, decrease their battery by 1 (not below 0).
  3. Return the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int countTestedDevices(vector<int>& batteryPercentages) {
        int n = batteryPercentages.size(), ans = 0;
        for (int i = 0; i < n; ++i) {
            if (batteryPercentages[i] > 0) {
                ans++;
                for (int j = i+1; j < n; ++j) {
                    batteryPercentages[j] = max(0, batteryPercentages[j] - 1);
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

type Solution struct{}
func (Solution) CountTestedDevices(batteryPercentages []int) int {
    n := len(batteryPercentages)
    ans := 0
    for i := 0; i < n; i++ {
        if batteryPercentages[i] > 0 {
            ans++
            for j := i+1; j < n; j++ {
                if batteryPercentages[j] > 0 {
                    batteryPercentages[j]--
                }
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int countTestedDevices(int[] batteryPercentages) {
        int n = batteryPercentages.length, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (batteryPercentages[i] > 0) {
                ans++;
                for (int j = i+1; j < n; ++j) {
                    if (batteryPercentages[j] > 0) batteryPercentages[j]--;
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun countTestedDevices(batteryPercentages: IntArray): Int {
        val n = batteryPercentages.size
        var ans = 0
        for (i in 0 until n) {
            if (batteryPercentages[i] > 0) {
                ans++
                for (j in i+1 until n) {
                    if (batteryPercentages[j] > 0) batteryPercentages[j]--
                }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def countTestedDevices(self, batteryPercentages: list[int]) -> int:
        n = len(batteryPercentages)
        ans = 0
        for i in range(n):
            if batteryPercentages[i] > 0:
                ans += 1
                for j in range(i+1, n):
                    if batteryPercentages[j] > 0:
                        batteryPercentages[j] -= 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn count_tested_devices(battery_percentages: Vec<i32>) -> i32 {
        let mut arr = battery_percentages.clone();
        let n = arr.len();
        let mut ans = 0;
        for i in 0..n {
            if arr[i] > 0 {
                ans += 1;
                for j in i+1..n {
                    if arr[j] > 0 {
                        arr[j] -= 1;
                    }
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    countTestedDevices(batteryPercentages: number[]): number {
        const n = batteryPercentages.length;
        let ans = 0;
        for (let i = 0; i < n; ++i) {
            if (batteryPercentages[i] > 0) {
                ans++;
                for (let j = i+1; j < n; ++j) {
                    if (batteryPercentages[j] > 0) batteryPercentages[j]--;
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), where n is the number of devices, since for each device we may update all subsequent devices.
  • 🧺 Space complexity: O(1), in-place modification.