Sponsored
Sponsored
First, calculate the total required sum for n + m rolls to satisfy the given mean. Then, compute the sum of the already available rolls and determine how much more is needed from the n missing rolls. If the required sum for the missing rolls is feasible (i.e., between n and 6*n), distribute the required sum across the missing rolls aiming for an even distribution.
The time complexity is O(n + m), where n and m are the number of missing and known observations, respectively, due to the sum calculations and array operations. The space complexity is O(n), for the storage of the missing rolls.
1def missingRolls(rolls, mean, n):
2 m = len(rolls)
3 total_sum = mean * (n + m)
4 current_sum = sum(rolls)
5 missing_sum = total_sum - current_sum
6 if missing_sum < n or missing_sum > 6 * n:
7 return []
8 base = missing_sum // n
9 remainder = missing_sum % n
10 result = [base + 1] * remainder + [base] * (n - remainder)
11 return resultIn this Python solution, we first calculate the total_sum that is needed by multiplying mean with n + m. We then subtract the current_sum of the known rolls from total_sum to find missing_sum, which represents the sum needed from the missing rolls. If missing_sum is not feasible (not between n and 6 * n), we return an empty array. Otherwise, we distribute the missing_sum into parts to create the missing rolls.
This approach iteratively builds the missing rolls by ensuring each additional roll keeps the total sum within possible bounds. Start with an empty list for the missing rolls, and iteratively add values ensuring the sum remains feasible, adjusting at each step.
The time complexity is O(n + m) due to the sum calculation and iteration over the missing rolls. The space complexity is O(n) for the missing rolls' storage.
1#include <vector>
2using namespace std;
3
4vector<int> missingRolls(vector<int>& rolls, int mean, int n) {
5 int m = rolls.size();
int totalSum = mean * (n + m);
int currentSum = accumulate(rolls.begin(), rolls.end(), 0);
int missingSum = totalSum - currentSum;
if (missingSum < n || missingSum > 6 * n) return {};
vector<int> result(n, 1);
missingSum -= n;
for (int i = 0; i < n && missingSum > 0; ++i) {
int add = min(missingSum, 5);
result[i] += add;
missingSum -= add;
}
return result;
}In this C++ solution, we accumulate the currentSum using std::accumulate. If the calculated missingSum is valid, we initialize a result vector with all ones. We then iteratively increase each entry by a maximum possible value (up to 5, since each die can have a maximum value of 6) until the missing sum is fulfilled.