Find Missing Observations

medium array math greedy

Problem

You rolled a die n + m times. You only kept m of the rolls (the array rolls); n rolls went missing. Given the overall target mean of all n + m rolls, return any array of n values (each from 1 to 6) that makes the average of all n + m rolls exactly mean. If no such array exists, return an empty array.

Inputrolls = [3,2,4,3], mean = 4, n = 2

Output[6,6]

Total sum must be 4 × 6 = 24. Known rolls sum to 12, so the 2 missing rolls must sum to 12, giving [6,6].

Inputrolls = [1,2,3,4], mean = 6, n = 4

Output[]

The missing sum would have to be 38, but 4 dice can total at most 24, so it is impossible.

rolls (comma-separated, each 1..6)

mean (1..6)

n (number of missing rolls)

def missing_rolls(rolls, mean, n):
    m = len(rolls)
    total = mean * (n + m)
    missing = total - sum(rolls)
    if missing < n or missing > 6 * n:
        return []
    base, rem = divmod(missing, n)
    ans = [base] * n
    for i in range(rem):
        ans[i] += 1
    return ans

function missingRolls(rolls, mean, n) {
  const m = rolls.length;
  const total = mean * (n + m);
  const missing = total - rolls.reduce((a, b) => a + b, 0);
  if (missing < n || missing > 6 * n) return [];
  const base = Math.floor(missing / n), rem = missing % n;
  const ans = new Array(n).fill(base);
  for (let i = 0; i < rem; i++) {
    ans[i] += 1;
  }
  return ans;
}

int[] missingRolls(int[] rolls, int mean, int n) {
    int m = rolls.length;
    int total = mean * (n + m);
    int sum = 0;
    for (int r : rolls) sum += r;
    int missing = total - sum;
    if (missing < n || missing > 6 * n) return new int[0];
    int base = missing / n, rem = missing % n;
    int[] ans = new int[n];
    for (int i = 0; i < n; i++) ans[i] = base + (i < rem ? 1 : 0);
    return ans;
}

vector<int> missingRolls(vector<int>& rolls, int mean, int n) {
    int m = rolls.size();
    int total = mean * (n + m);
    int sum = 0;
    for (int r : rolls) sum += r;
    int missing = total - sum;
    if (missing < n || missing > 6 * n) return {};
    int base = missing / n, rem = missing % n;
    vector<int> ans(n, base);
    for (int i = 0; i < rem; i++) ans[i] += 1;
    return ans;
}

Explanation

The average of all n + m rolls is the total sum divided by n + m. So if the mean must equal mean, the total sum is fixed: total = mean × (n + m).

We already know the sum of the visible rolls, so the sum the missing rolls must contribute is missing = total − sum(rolls). Everything reduces to: can n dice add up to missing?

n dice can sum to anything between n (all ones) and 6n (all sixes). If missing falls outside [n, 6n] the answer is impossible, so we return an empty array.

Otherwise we just spread missing as evenly as possible. With base = missing // n and remainder rem = missing % n, give rem of the dice the value base + 1 and the rest base. Because n ≤ missing ≤ 6n, base lands in 1..6 and base + 1 stays ≤ 6, so every value is a legal die face.

Example: rolls = [3,2,4,3], mean = 4, n = 2. Total must be 4 × 6 = 24; visible rolls sum to 12, so the two missing rolls must sum to 12. Spreading 12 over 2 dice gives [6, 6].

Time: O(n + m) Space: O(n)