This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE
2028. Find Missing Observations
Difficulty: Medium
Topics: Array, Math, Simulation
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 + mrolls 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 <= 6
Hint:
- What should the sum of the n rolls be?
- Could you generate an array of size n such that each element is between 1 and 6?
Solution:
We need to determine an array of missing rolls such that the average of all n + m dice rolls is exactly equal to mean. Here's the step-by-step breakdown of the solution:
Steps to Approach:
Calculate the total sum for
n + mrolls:
Given that the average value ofn + mrolls ismean, the total sum of all the rolls should betotal_sum = (n + m) * mean.Determine the missing sum:
The sum of themrolls is already known. Thus, the sum of the missingnrolls should be:
missing_sum = total_sum - ∑(rolls)
where ∑(rolls) is the sum of the elements in the rolls array.
-
Check for feasibility:
Each roll is a 6-sided die, so the missing values must be between 1 and 6 (inclusive). Therefore, the sum of the missing
nrolls must be between:
min_sum = n X 1 = n
and
max_sum = n X 6 = 6n
If the missing_sum is outside this range, it's impossible to form valid missing observations, and we should return an empty array.
-
Distribute the missing sum:
If
missing_sumis valid, we distribute it across thenrolls by initially filling each element with1(the minimum possible value). Then, we increment elements from 1 to 6 until we reach the requiredmissing_sum.
Let's implement this solution in PHP: 2028. Find Missing Observations
<?php
/**
* @param Integer[] $rolls
* @param Integer $mean
* @param Integer $n
* @return Integer[]
*/
function missingRolls($rolls, $mean, $n) {
...
...
...
/**
* go to ./solution.php
*/
}
// Example 1
$rolls = [3, 2, 4, 3];
$mean = 4;
$n = 2;
print_r(missingRolls($rolls, $mean, $n));
// Example 2
$rolls = [1, 5, 6];
$mean = 3;
$n = 4;
print_r(missingRolls($rolls, $mean, $n));
// Example 3
$rolls = [1, 2, 3, 4];
$mean = 6;
$n = 4;
print_r(missingRolls($rolls, $mean, $n));
?>
Explanation:
-
Input:
rolls = [3, 2, 4, 3]mean = 4n = 2
-
Steps:
- The total number of rolls is
n + m = 6. - The total sum needed is
6 * 4 = 24. - The sum of the given rolls is
3 + 2 + 4 + 3 = 12. - The sum required for the missing rolls is
24 - 12 = 12.
- The total number of rolls is
We need two missing rolls that sum up to 12, and the only possibility is [6, 6].
-
Result:
- For example 1: The output is
[6, 6]. - For example 2: The output is
[2, 3, 2, 2]. - For example 3: No valid solution, so the output is
[].
- For example 1: The output is
Time Complexity:
- Calculating the sum of
rollstakes O(m), and distributing themissing_sumtakes O(n). Hence, the overall time complexity is O(n + m), which is efficient for the input constraints.
This solution ensures that we either find valid missing rolls or return an empty array when no solution exists.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE
MD ARIFUL HAQUE | Sciencx (2024-09-05T22:23:28+00:00) 2028. Find Missing Observations. Retrieved from https://www.scien.cx/2024/09/05/2028-find-missing-observations/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.