⚡Flashcard Drill➔
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

  1. The total sum of all n + m rolls is mean * (n + m), so the missing observations must sum to rem = mean * (n + m) - sum(rolls).
  2. Feasibility is exactly n <= rem <= 6 * n: the smallest possible missing sum is n (all ones) and the largest is 6 * n (all sixes).
  3. Construct the answer by spreading rem as evenly as possible: base, extra = divmod(rem, n), producing extra copies of base + 1 and n - extra copies of base.
  4. 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: rem can fall below n or above 6 * n, in which case no dice assignment exists and the empty array is required.
  • Reading mean as the average of the known rolls only: mean is the average of all n + m observations, 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.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems