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 <= 6First, 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.
Java
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.
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.
| 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. |
4 Leetcode Mistakes • Sahil & Sarra • 421,929 views views
Watch 9 more video solutions →Practice Find Missing Observations with our built-in code editor and test cases.
Practice on FleetCode