Count Valid Cleanup Plans
A neighborhood is organizing a cleanup day. Every resident must decide whether to join the cleanup or stay home.
Each resident has a minimum companion requirement. Count the cleanup plans in which every resident's decision satisfies their requirement.
Implement the following method:
int countValidCleanupPlans(List<Integer> companionNeeds)
companionNeeds.get(i) is the minimum number of other participating residents required by resident i.- The method returns the number of valid cleanup plans.
Rules
- Every resident must either join the cleanup or stay home.
- If resident
i joins, at least companionNeeds.get(i) other residents must also join.
- If resident
i stays home, the total number of participating residents must be strictly less than companionNeeds.get(i).
- A plan is valid only if every resident satisfies the applicable rule.
- Two plans are different if at least one resident makes a different decision.
Constraints
1 ≤ companionNeeds.size() ≤ 100,000 0 ≤ companionNeeds.get(i) < companionNeeds.size() companionNeeds never contains null values.
Examples
Example 1
countValidCleanupPlans( companionNeeds = List.of(0, 2, 2, 4, 6, 6, 6) )
Output: 3
Valid plans have 1, 3, or 7 participating residents.
Example 2
countValidCleanupPlans( companionNeeds = List.of(2, 2, 4, 4, 4) )
Output: 2
The valid plans are for everyone to stay home or for all five residents to join.
Example 3
countValidCleanupPlans( companionNeeds = List.of(0, 1, 2, 3, 4, 5) )
Output: 1
The only valid plan has all six residents joining. Every smaller group contains a resident whose requirement makes both decisions invalid.
Example 4
countValidCleanupPlans( companionNeeds = List.of(0, 0, 5, 5, 5, 5) )
Output: 2
One valid plan has only the two residents with requirement 0 joining. The other valid plan has all six residents joining.