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.
Example 4:
Input: rolls = [1], mean = 3, n = 1 Output: [5] Explanation: The mean of all n + m rolls is (1 + 5) / 2 = 3.
Constraints:
m == rolls.length
1 <= n, m <= 105
1 <= rolls[i], mean <= 6
Solution: Math & Greedy
Total sum = (m + n) * mean
Left = Total sum – sum(rolls) = (m + n) * mean – sum(rolls)
If left > 6 * n or left < 1 * n, then there is no solution.
Otherwise, we need to distribute Left into n rolls.
There are very ways to do that, one of them is even distribution, e.g. using the average number as much as possible, and use avg + 1 to fill the gap.
Compute the average and reminder: x = left / n, r = left % n.
there will be n – r of x and r of x + 1 in the output array.
e.g. [1, 5, 6], mean = 3, n = 4
Total sum = (3 + 4) * 3 = 21
Left = 21 – (1 + 5 + 6) = 9
x = 9 / 4 = 2, r = 9 % 4 = 1
Ans = [2, 2, 2, 2+1] = [2,2,2,3]
Time complexity: O(m + n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution { public: vector<int> missingRolls(vector<int>& rolls, int mean, int n) { const int m = rolls.size(); int t = accumulate(begin(rolls), end(rolls), 0); int left = mean * (m + n) - t; if (left > 6 * n || left < n) return {}; vector<int> ans(n, left / n); for (int i = 0; i < left % n; ++i) ++ans[i]; return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment