We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Tested Devices After Test Operations

Number: 3220

Difficulty: Easy

Paid? No

Companies: Accenture

Problem Description

Given an array batteryPercentages representing the battery levels of n devices, the goal is to simulate a series of test operations. For each device, if its battery percentage is greater than 0, consider it tested (increment the count) and then reduce the battery percentage of every subsequent device by 1 (ensuring no negative values). The devices are processed in order, and the task is to return the total number of devices that get tested.

Key Insights

  • Process devices sequentially from index 0 to n-1.
  • A device is only tested if its current battery percentage is greater than 0.
  • When a device is tested, decrease the battery percentage of all devices with a higher index by 1, but never below 0.
  • The simulation modifies the array in-place, meaning future decisions are affected by previous battery reductions.

Space and Time Complexity

Time Complexity: O(n^2) in the worst-case scenario since for each tested device, subsequent elements are updated.
Space Complexity: O(1) extra space (in-place modification of the input array).

Solution

The approach involves iterating through the batteryPercentages array and for each device that has a battery greater than 0, counting it as tested and then iterating through all subsequent devices to reduce their battery by 1 (using a max function to prevent negative values). This simulation is straightforward given the constraints (n up to 100), and the in-place modification allows us to work with constant extra space.

Code Solutions

# Function to count tested devices based on battery percentages
def countTestedDevices(batteryPercentages):
    # Initialize counter for tested devices
    tested_count = 0
    n = len(batteryPercentages)
    # Process each device sequentially
    for i in range(n):
        # If current device has battery greater than 0, it can be tested
        if batteryPercentages[i] > 0:
            tested_count += 1
            # Reduce battery percentage of all subsequent devices by 1, not going below 0
            for j in range(i + 1, n):
                batteryPercentages[j] = max(0, batteryPercentages[j] - 1)
    return tested_count

# Example usage:
print(countTestedDevices([1, 1, 2, 1, 3]))  # Expected output: 3
← Back to All Questions