Press "Enter" to skip to content

花花酱 LeetCode 2028. Find Missing Observations

You have observations of n + m 6-sided dice rolls with each face numbered from 1 to 6n 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++

请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website
您可以通过在亚马逊上购物(任意商品)来支持我们

Paypal
Venmo
huahualeetcode
微信打赏

Be First to Comment

Leave a Reply