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.
First, calculate the total required sum for n + m rolls to satisfy the given mean. Then, compute the sum of the already available rolls and determine how much more is needed from the n missing rolls. If the required sum for the missing rolls is feasible (i.e., between n and 6*n), distribute the required sum across the missing rolls aiming for an even distribution.
In this Python solution, we first calculate the total_sum that is needed by multiplying mean with n + m. We then subtract the current_sum of the known rolls from total_sum to find missing_sum, which represents the sum needed from the missing rolls. If missing_sum is not feasible (not between n and 6 * n), we return an empty array. Otherwise, we distribute the missing_sum into parts to create the missing rolls.
The time complexity is O(n + m), where n and m are the number of missing and known observations, respectively, due to the sum calculations and array operations. The space complexity is O(n), for the storage of the missing rolls.
This approach iteratively builds the missing rolls by ensuring each additional roll keeps the total sum within possible bounds. Start with an empty list for the missing rolls, and iteratively add values ensuring the sum remains feasible, adjusting at each step.
In this C++ solution, we accumulate the currentSum using std::accumulate. If the calculated missingSum is valid, we initialize a result vector with all ones. We then iteratively increase each entry by a maximum possible value (up to 5, since each die can have a maximum value of 6) until the missing sum is fulfilled.
C++
JavaScript
The time complexity is O(n + m) due to the sum calculation and iteration over the missing rolls. The space complexity is O(n) for the missing rolls' storage.
According to the problem description, the sum of all numbers is (n + m) times mean, and the sum of known numbers is sum_{i=0}^{m-1} rolls[i]. Therefore, the sum of the missing numbers is s = (n + m) times mean - sum_{i=0}^{m-1} rolls[i].
If s \gt n times 6 or s \lt n, it means there is no answer that satisfies the conditions, so we return an empty array.
Otherwise, we can evenly distribute s to n numbers, that is, the value of each number is s / n, and the value of s bmod n numbers is increased by 1.
The time complexity is O(n + m), where n and m are the number of missing numbers and known numbers, respectively. Ignoring the space consumption of the answer, the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Calculate Missing Sum and Distribute Among Rolls | The time complexity is O(n + m), where n and m are the number of missing and known observations, respectively, due to the sum calculations and array operations. The space complexity is O(n), for the storage of the missing rolls. |
| Iterative Construction of Missing Rolls | The time complexity is O(n + m) due to the sum calculation and iteration over the missing rolls. The space complexity is O(n) for the missing rolls' storage. |
| Construction | — |
| 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. |
Find Missing Observations - Leetcode 2028 Weekly Contest Problem - Python • NeetCode • 10,385 views views
Watch 9 more video solutions →Practice Find Missing Observations with our built-in code editor and test cases.
Practice on FleetCode