Find Missing Observations

How it works

Instead of greedily assigning values one at a time, we can distribute the required sum more evenly. First, compute the average value each die should have by dividing the total needed by n. The remainder tells us how many dice need to be one higher than the average. This produces a cleaner distribution where most dice have the same value.

Steps

1. Calculate the required sum for the n missing dice: nTotal = mean * (n + m) - sum(rolls).
2. If nTotal < n or nTotal > 6 * n, return an empty array.
3. Compute the base average: avg = nTotal / n.
4. Compute the remainder: rem = nTotal - (avg * n).
5. Create the result with (n - rem) dice having value avg and rem dice having value avg + 1.
6. Return the result array.

Complexity

• Time complexity: O(m + n)
• Space complexity:
  • O(1) extra space.
  • O(n) space for the output array.

Where m is the size of the array rolls and n is the number of missing observations.

Things to watch for

Forgetting to Validate the Required Sum

Before constructing the result, you must check that nTotal (the required sum for missing dice) falls within the valid range [n, 6*n]. If nTotal < n, it is impossible to assign at least 1 to each die. If nTotal > 6*n, it is impossible even if all dice show 6. Failing to return an empty array in these cases leads to incorrect or invalid outputs.

Integer Overflow When Computing Total Sum

When calculating mean * (n + m), both n and m can be large (up to 10^5), and the mean can be up to 6. The product can exceed the range of 32-bit integers in some languages. Ensure you use appropriate data types (e.g., long in Java) or rely on languages with arbitrary precision integers to avoid overflow.

Off-by-One Errors in Greedy Assignment

When greedily assigning values, the formula min(nTotal - remaining + 1, 6) requires careful handling of the remaining count. If you decrement the count at the wrong time or miscalculate how much "room" is left for future dice, you may assign invalid values (less than 1 or greater than 6) or fail to distribute the sum correctly.

from typing import List

class Solution:
    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:
        m = len(rolls)
        nTotal = (mean * (n + m)) - sum(rolls)

        if nTotal < n or nTotal > n * 6:
            return []

        avg = nTotal // n
        rem = nTotal - (avg * n)
        return [avg] * (n - rem) + [avg + 1] * rem

class Solution {
public:
    vector<int> missingRolls(vector<int>& rolls, int mean, int n) {
        int m = rolls.size();
        int nTotal = (mean * (n + m)) - accumulate(rolls.begin(), rolls.end(), 0);

        if (nTotal < n || nTotal > n * 6) {
            return {};
        }

        int avg = nTotal / n;
        int rem = nTotal - (avg * n);
        vector<int> res;

        for (int i = 0; i < n - rem; ++i) {
            res.push_back(avg);
        }
        for (int i = 0; i < rem; ++i) {
            res.push_back(avg + 1);
        }

        return res;
    }
};