FastPrep
Problem · Array

Warehouse Robots with Threshold

Learn this problem
● MediumAmazonINTERNOA
See Amazon hiring insights

Problem statement

You are given an integer array arr of size n, where arr[i] represents the threshold of the i-th robot. Each robot can be assigned one of two states: Running or Waiting.

A configuration is valid if all robots satisfy the following conditions:

  • If a robot is Running, then the total number of running robots must be ≥ arr[i].
  • If a robot is Waiting, then the total number of waiting robots must be < arr[i].

Each robot must be assigned exactly one state. A configuration is valid only if no robot violates its condition.

Return the total number of valid configurations.

Function

countValidConfigurations(arr: int[]) → int

Examples

Example 1

arr = [1,2]return = 2
n=2. Config 1: robot-0 Running, robot-1 Waiting. Running count=1 >= arr[0]=1 ✓. Waiting count=1 < arr[1]=2 ✓. Valid. Config 2: both Running. Running count=2 >= arr[0]=1 ✓, 2 >= arr[1]=2 ✓. No waiting robots to check. Valid. Config "both Waiting": waiting count=2, robot-0 needs 2 < arr[0]=1 ✗. Invalid. Config "robot-1 Running only": running count=1 >= arr[1]=2? 1 >= 2 ✗. Invalid. Total = 2.

Example 2

arr = [2,2]return = 1
n=2. Both Running: running count=2 >= arr[0]=2 ✓, 2 >= arr[1]=2 ✓. Valid. All other configs fail: running count 0 or 1 cannot satisfy arr[i]=2 for a Running robot, and waiting count 1 or 2 cannot satisfy < arr[i]=2 for a Waiting robot (1 < 2 ✓ but a single Running robot fails its own condition). Total = 1.

Constraints

  • 1 <= n <= 10^5
  • 1 <= arr[i] <= n

    • More Amazon problems

    drafts saved locally
    public int countValidConfigurations(int[] arr) {
  // write your code here
}
    arr[1,2]
    expected2
    checking account