2028. Find Missing Observations
Description
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.length
1 <= n, m <= 105
1 <= rolls[i], mean <= 6
Solutions
Solution 1: Construction
According to the problem description, the sum of all numbers is $(n + m) \times mean$, and the sum of known numbers is sum(rolls)
. Therefore, the sum of the missing numbers is $s = (n + m) \times mean - sum(rolls)$.
If $s > n \times 6$ or $s < n$, it means there is no answer that satisfies the conditions, so 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)$, and the space complexity is $O(1)$. Here, $n$ and $m$ are the number of missing numbers and known numbers, respectively.
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
|