NeetCode #925LC-2028MediumMath & Geometry
← Back to All Problems#925 · #2028 · Find Missing Observations(找出缺失的观测数据)
📌 Problem Statement & Constraints
Given an array
rolls of m dice observations (each in 1..6) plus integers mean and n, the n + m total observations average exactly mean. Return any length-n array of missing observations, each in 1..6, or an empty array if none exists. Constraints: 1 <= n, m <= 10^5, 1 <= mean <= 6, 1 <= rolls[i] <= 6.💡 Core Algorithmic Approaches
- The total sum of all
n + mrolls ismean * (n + m), so the missing observations must sum torem = mean * (n + m) - sum(rolls). - Feasibility is exactly
n <= rem <= 6 * n: the smallest possible missing sum isn(all ones) and the largest is6 * n(all sixes). - Construct the answer by spreading
remas evenly as possible:base, extra = divmod(rem, n), producingextracopies ofbase + 1andn - extracopies ofbase. - The feasibility bound guarantees
1 <= base <= base + 1 <= 6, so the even spread is always a legal dice assignment.
💻 Benchmark Python3 Implementation
class Solution:
def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:
total = mean * (len(rolls) + n)
rem = total - sum(rolls)
if rem < n or rem > 6 * n: # each observation must be in [1, 6]
return []
base, extra = divmod(rem, n)
return [base + 1] * extra + [base] * (n - extra)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n + m): one pass to sum rolls plus O(n) to build the result.
💾 Space Complexity
O(n): the returned array (the input is only read).
⚠️ Interview Pitfalls & Follow-ups
- Skipping the feasibility test:
remcan fall belownor above6 * n, in which case no dice assignment exists and the empty array is required. - Reading
meanas the average of the known rolls only:meanis the average of alln + mobservations, so the total must include the missing ones. - Greedily filling sixes then ones: it also yields a valid answer but is more code; the even spread lands in range automatically.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.