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.
1import java.util.*;
2
3public class Solution {
4 public int[] missingRolls(int[] rolls, int mean, int n) {
5 int m = rolls.length;
6 int totalSum = mean * (n + m);
7 int currentSum = 0;
8 for (int roll : rolls) {
9 currentSum += roll;
10 }
11 int missingSum = totalSum - currentSum;
12 if (missingSum < n || missingSum > 6 * n) {
13 return new int[0];
14 }
15 int base = missingSum / n;
16 int remainder = missingSum % n;
17 int[] result = new int[n];
18 for (int i = 0; i < n; i++) {
19 result[i] = (i < remainder) ? base + 1 : base;
20 }
21 return result;
22 }
23}In the Java implementation, the idea remains the same: calculate the totalSum, subtract currentSum from totalSum to get missingSum, and verify its feasibility. If feasible, distribute the remainder evenly across the missing rolls array.
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.