Leetcode 2028: Find Missing Observations
You are given an array of
m observations, each representing a die roll from a 6-sided die, and an average value mean of all n + m rolls. Your task is to calculate the missing n observations such that the overall average of all n + m rolls equals the provided mean. If multiple valid answers exist, return any of them. If it is impossible to achieve the desired average, return an empty array.Problem
Approach
Steps
Complexity
Input: The input consists of an array `rolls` representing `m` observed die rolls, and two integers `mean` and `n`, where `n` is the number of missing rolls.
Example: rolls = [1, 2, 3], mean = 4, n = 3
Constraints:
• 1 <= rolls.length <= 10^5
• 1 <= rolls[i], mean <= 6
Output: Return an array containing the `n` missing observations such that the average of all `n + m` rolls is equal to `mean`. If no such array exists, return an empty array.
Example: Output: [5, 5, 5]
Constraints:
• If multiple solutions exist, any valid array is acceptable.
• If it's impossible to achieve the desired mean, return an empty array.
Goal: The goal is to determine the missing `n` observations whose sum, together with the sum of the observed rolls, results in the exact average of `mean`.
Steps:
• 1. Compute the required sum of all `n + m` rolls by multiplying the mean by `n + m`.
• 2. Subtract the sum of the observed rolls from the required sum to get the sum of the missing rolls.
• 3. Check if the sum of the missing rolls is feasible (i.e., within the possible range of `n` die rolls).
• 4. If feasible, divide the sum by `n` to get the average roll value for the missing rolls and distribute any remainder evenly across the missing rolls.
Goal: Constraints for input values and operations.
Steps:
• 1 <= rolls.length <= 10^5
• 1 <= rolls[i], mean <= 6
Assumptions:
• The value of `mean` is an integer and the sum of all rolls should be divisible by `n + m`.
• Input: rolls = [1, 2, 3], mean = 4, n = 3
• Explanation: The total sum needed is (1 + 2 + 3 + 5 + 5 + 5) = 24, and the average is 24 / 6 = 4.
• Input: rolls = [1, 5, 6], mean = 3, n = 4
• Explanation: The total sum needed is (1 + 5 + 6 + 2 + 3 + 2 + 2) = 21, and the average is 21 / 7 = 3.
• Input: rolls = [1, 2, 3, 4], mean = 6, n = 4
• Explanation: It is impossible to achieve an average of 6 because the sum would be too large for the missing rolls to fit the required range.
Approach: To solve this problem, we need to determine the sum of the missing `n` rolls and ensure it fits within the possible range for `n` dice rolls. We then distribute this sum evenly and handle any remainder appropriately.
Observations:
• The sum of the missing rolls should be between `n` and `6 * n` (because each roll is between 1 and 6).
• We can compute the required sum and divide it evenly. The remainder can be distributed across the missing rolls.
Steps:
• 1. Calculate the total sum required for the `n + m` rolls.
• 2. Subtract the sum of the observed rolls from the total sum to get the sum for the missing rolls.
• 3. Check if the sum of the missing rolls is valid (between `n` and `6 * n`).
• 4. Distribute the sum among the missing rolls, adding extra values to some rolls if needed.
Empty Inputs:
• Not applicable as `rolls` cannot be empty.
Large Inputs:
• Ensure the solution is efficient enough for large inputs (up to 10^5).
Special Values:
• If `mean` is not achievable based on the sum of the rolls, return an empty array.
Constraints:
• Ensure the solution runs within time limits for large inputs.
vector<map<int, bool>> memo;
vector<int> missingRolls(vector<int>& rolls, int mean, int n) {
int m = rolls.size();
int sum = 0;
for(int i = 0; i < m; i++)
sum += rolls[i];
int net = mean * (m + n);
sum = net - sum;
// create an array of size n with sum = sum and elements 1 - 6
if(sum < n || sum > 6 * n) return vector<int>{};
int x = sum / n, rem = sum % n;
vector<int> res(n, x);
for(int i = 0; i < rem; i++) {
res[i]++;
}
return res;
}
1 : Variable Declaration
vector<map<int, bool>> memo;
A memoization table is declared, but it is not used in this function. It might be intended for optimization in case of complex cases.
2 : Function Definition
vector<int> missingRolls(vector<int>& rolls, int mean, int n) {
This defines the function 'missingRolls' that takes a vector of rolls, the mean value, and the number of missing rolls 'n'. It returns a vector containing the missing rolls that would satisfy the mean.
3 : Array Size
int m = rolls.size();
This calculates the size of the 'rolls' vector to determine how many rolls have already been made.
4 : Sum Initialization
int sum = 0;
This initializes a variable 'sum' to accumulate the total of the current rolls.
5 : Loop Start
for(int i = 0; i < m; i++)
This starts a loop to iterate over each of the current rolls.
6 : Accumulate Rolls
sum += rolls[i];
This adds the value of the current roll to the 'sum' variable.
7 : Net Calculation
int net = mean * (m + n);
This calculates the total sum required to achieve the given mean, based on the number of rolls (m) and missing rolls (n).
8 : Sum Adjustment
sum = net - sum;
This adjusts the sum to reflect the remaining total needed to achieve the required mean.
9 : Condition Check
if(sum < n || sum > 6 * n) return vector<int>{};
This checks if the sum is impossible to achieve with 'n' rolls. If the sum is less than 'n' or greater than the maximum possible sum (6 * n), it returns an empty vector.
10 : Variable Initialization
int x = sum / n, rem = sum % n;
This calculates the base value 'x' that each roll will have and the remainder 'rem' that needs to be distributed across the rolls.
11 : Vector Initialization
vector<int> res(n, x);
This initializes the result vector 'res' of size 'n', with each element set to the base value 'x'.
12 : Loop Start
for(int i = 0; i < rem; i++) {
This starts a loop to distribute the remainder 'rem' across the result vector.
13 : Distribute Remainder
res[i]++;
This increments the first 'rem' elements of the result vector by 1 to properly distribute the remainder.
14 : Return Statement
return res;
This returns the result vector containing the missing rolls that satisfy the mean.
Best Case: O(n + m)
Average Case: O(n + m)
Worst Case: O(n + m)
Description: The algorithm runs in linear time relative to the number of rolls and missing observations.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is linear, as we need to store the missing rolls.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus