Watch 10 video solutions for Find Missing Observations, a medium level problem involving Array, Math, Simulation. This walkthrough by NeetCode has 10,385 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You have observations of n + m 6-sided dice rolls with each face numbered from 1 to 6. n of the observations went missing, and you only have the observations of m rolls. Fortunately, you have also calculated the average value of the n + m rolls.
You are given an integer array rolls of length m where rolls[i] is the value of the ith observation. You are also given the two integers mean and n.
Return an array of length n containing the missing observations such that the average value of the n + m rolls is exactly mean. If there are multiple valid answers, return any of them. If no such array exists, return an empty array.
The average value of a set of k numbers is the sum of the numbers divided by k.
Note that mean is an integer, so the sum of the n + m rolls should be divisible by n + m.
Example 1:
Input: rolls = [3,2,4,3], mean = 4, n = 2 Output: [6,6] Explanation: The mean of all n + m rolls is (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4.
Example 2:
Input: rolls = [1,5,6], mean = 3, n = 4 Output: [2,3,2,2] Explanation: The mean of all n + m rolls is (1 + 5 + 6 + 2 + 3 + 2 + 2) / 7 = 3.
Example 3:
Input: rolls = [1,2,3,4], mean = 6, n = 4 Output: [] Explanation: It is impossible for the mean to be 6 no matter what the 4 missing rolls are.
Constraints:
m == rolls.length1 <= n, m <= 1051 <= rolls[i], mean <= 6Problem Overview: You are given several observed dice rolls and the overall mean of all rolls (observed + missing). Each roll is between 1 and 6. The task is to reconstruct the n missing rolls so the final average matches the given mean. If it is impossible to form valid dice values, return an empty array.
Approach 1: Calculate Missing Sum and Distribute Among Rolls (Time: O(m + n), Space: O(n))
This approach relies on simple math and array operations. First compute the total sum required for all rolls using mean * (m + n), where m is the number of observed rolls. Subtract the sum of the observed array to get the total value the missing rolls must contribute. If this value is outside the feasible range [n, 6n], there is no valid solution because dice values must stay between 1 and 6.
Once the required sum is valid, distribute it across n elements. Start by assigning the base value missingSum // n to each position and distribute the remainder by incrementing elements by one until the total matches the required sum. This guarantees all values remain within bounds while keeping the distribution balanced. The algorithm performs a single pass over the input and builds the result array directly.
Approach 2: Iterative Construction of Missing Rolls (Time: O(m + n), Space: O(n))
This method builds the missing sequence step by step using a greedy simulation. Compute the total missing sum the same way as the previous approach. Instead of evenly distributing values immediately, iterate through the n positions and assign a value that keeps the remaining sum feasible for the remaining slots.
At each step, choose the smallest valid value that still allows the remaining positions to stay within the dice bounds. For example, if you place x, ensure the remaining sum can still fall within [remainingSlots, 6 * remainingSlots]. This constraint check guarantees that future assignments remain valid. The process continues until all n values are assigned or the constraints fail.
This approach is useful when you want explicit control over each assignment or when explaining feasibility constraints during interviews. It makes the reasoning about bounds very clear, though it performs the same number of operations as the direct distribution method.
Recommended for interviews: The missing sum distribution approach is the most common solution because it reduces the problem to a straightforward arithmetic constraint and balanced allocation. Interviewers expect you to first verify the feasibility range [n, 6n] and then construct the result in linear time. Demonstrating the iterative feasibility check also shows strong reasoning about constraints and edge cases.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Calculate Missing Sum and Distribute | O(m + n) | O(n) | General case. Clean mathematical solution with minimal logic. |
| Iterative Construction of Missing Rolls | O(m + n) | O(n) | When explaining feasibility constraints step-by-step or simulating assignments. |