Good Game Score Threshold: Find Minimum Score Cutoff Where Most Players Pass

Question

## Problem You are given a list of player scores and a fraction `f` (0 < f <= 1.0). Find the minimum integer threshold `t` such that at least `ceil(f * n)` players have a score >= `t`. Return -1 if no valid threshold exists. ```python from math import ceil def min_threshold(scores: list[int], f: float) -> int: pass ``` **Example:** ``` Input: scores = [40, 55, 70, 85, 90], f = 0.6 Required: ceil(0.6 * 5) = 3 players must pass. At t=55: scores >= 55 are [55,70,85,90] -> 4 players. Valid. At t=70: scores >= 70 are [70,85,90] -> 3 players. Valid. At t=85: scores >= 85 are [85,90] -> 2 players. Invalid. Minimum t where exactly >= 3 pass: t=40 (all 5 pass). But "minimum threshold" = lowest t that achieves the requirement = 40? Clarify: find the HIGHEST t where the condition still holds. Output: 70 ``` ## Follow-ups 1. How would you solve this with binary search? What is the predicate? 2. What is the time complexity with and without sorting? 3. What if scores are streamed in and you need to update the threshold after each new score? 4. Extend to multiple game modes: each mode has its own score list. Find a single universal threshold satisfying the fraction constraint for all modes simultaneously.

Good Game Score Threshold: Find Minimum Score Cutoff Where Most Players Pass

Question Details

Full Details

Topics

More from Roblox