# Find Missing Observations
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-missing-observations)
Canonical: https://scaleengineer.com/dsa/problems/find-missing-observations
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
---
## Problem
You have observations of `n + m` **6-sided** dice rolls with each face numbered from `1` to `6`. `n` of the observations went missing, and you only have the observations of `m` rolls. Fortunately, you have also calculated the **average value** of the `n + m` rolls.

You are given an integer array `rolls` of length `m` where `rolls[i]` is the value of the `ith` observation. You are also given the two integers `mean` and `n`.

Return _an array of length_ `n` _containing the missing observations such that the **average value** of the_ `n + m` _rolls is **exactly**_ `mean`. If there are multiple valid answers, return _any of them_. If no such array exists, return _an empty array_.

The **average value** of a set of `k` numbers is the sum of the numbers divided by `k`.

Note that `mean` is an integer, so the sum of the `n + m` rolls should be divisible by `n + m`.

**Example 1:**

**Input:** rolls = [3,2,4,3], mean = 4, n = 2
**Output:** [6,6]
**Explanation:** The mean of all n + m rolls is (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4.

**Example 2:**

**Input:** rolls = [1,5,6], mean = 3, n = 4
**Output:** [2,3,2,2]
**Explanation:** The mean of all n + m rolls is (1 + 5 + 6 + 2 + 3 + 2 + 2) / 7 = 3.

**Example 3:**

**Input:** rolls = [1,2,3,4], mean = 6, n = 4
**Output:** []
**Explanation:** It is impossible for the mean to be 6 no matter what the 4 missing rolls are.

**Constraints:**

* `m == rolls.length`
* `1 <= n, m <= 105`
* `1 <= rolls[i], mean <= 6`

# Approaches
## Brute-Force with Backtracking
This approach involves exploring all possible combinations for the `n` missing dice rolls using recursion. For each of the `n` missing rolls, we try every possible value from 1 to 6. If a combination results in the desired total mean, we have found a solution. While this approach is conceptually straightforward, it is computationally very expensive.
**Time:** O(6^n) - In the worst case, the algorithm explores all `6^n` possible combinations for the `n` missing rolls. Pruning can reduce the search space in practice, but the worst-case complexity remains exponential. · **Space:** O(n) - The space is dominated by the recursion stack depth, which can go up to `n` in the worst case. We also need O(n) space to store the combination being built.
**Pros:** Guaranteed to find a solution if one exists.; Serves as a fundamental approach that can be applied to a wide range of combinatorial search problems.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' error for the given constraints where `n` can be up to 10^5.
### Explanation
First, we determine the required sum of the `n` missing rolls. The total sum of all `n + m` rolls is `mean * (n + m)`. By subtracting the sum of the known `m` rolls, we get the target sum for the missing `n` rolls, let's call it `missingSum`.

We then use a backtracking algorithm to find a sequence of `n` numbers (from 1 to 6) that add up to `missingSum`. The algorithm works as follows:

We define a recursive function that attempts to build the array of missing rolls one element at a time. For the first missing roll, it tries placing a 1, then recurses to find the rest of the sum. If that fails, it backtracks and tries placing a 2, and so on, up to 6.

To avoid unnecessary computation, we can add pruning to the backtracking function. At any step, if we know that it's impossible to reach `missingSum` from the current state (e.g., the remaining sum needed is too high or too low for the number of rolls left), we can stop exploring that path. Despite pruning, the worst-case time complexity remains exponential.

```java
class Solution {
    private int[] result;
    private int n_val;
    private int targetSum;

    public int[] missingRolls(int[] rolls, int mean, int n) {
        this.n_val = n;
        int m = rolls.length;
        int sum_m = 0;
        for (int roll : rolls) {
            sum_m += roll;
        }

        this.targetSum = mean * (n + m) - sum_m;

        if (targetSum < n || targetSum > 6 * n) {
            return new int[0];
        }

        this.result = null;
        findCombination(0, 0, new int[n]);
        return result == null ? new int[0] : result;
    }

    private boolean findCombination(int k, int currentSum, int[] combination) {
        if (k == n_val) {
            if (currentSum == targetSum) {
                this.result = combination.clone();
                return true;
            }
            return false;
        }

        // Pruning
        if (currentSum + (n_val - k) * 1 > targetSum || currentSum + (n_val - k) * 6 < targetSum) {
            return false;
        }

        for (int v = 1; v <= 6; v++) {
            combination[k] = v;
            if (findCombination(k + 1, currentSum + v, combination)) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- Calculate `m = rolls.length`.
- Calculate `sum_m`, the sum of elements in `rolls`.
- Calculate the target sum for the missing rolls: `missingSum = mean * (n + m) - sum_m`.
- Define a recursive backtracking function, e.g., `backtrack(index, currentSum, combination)`.
- The function tries to fill the `combination` array from the given `index`.
- **Base Case**: If `index == n`, check if `currentSum == missingSum`. If they match, a solution has been found. Store it and return `true`.
- **Recursive Step**: Iterate through dice values `v` from 1 to 6. For each `v`:
    - Place `v` at `combination[index]`.
    - Make a recursive call: `backtrack(index + 1, currentSum + v, combination)`.
    - If the recursive call returns `true`, it means a solution was found, so propagate `true` up the call stack.
- **Pruning**: Before the loop, add checks to prune impossible branches. If the minimum possible sum from the current state (`currentSum + (n - index) * 1`) is already greater than `missingSum`, or the maximum possible sum (`currentSum + (n - index) * 6`) is less than `missingSum`, then this path cannot lead to a solution, so return `false`.
- If the initial `missingSum` is impossible (i.e., less than `n` or greater than `6*n`), return an empty array immediately.

## Direct Mathematical Calculation and Distribution
This optimal approach avoids any form of exhaustive search by using a direct mathematical calculation. It first computes the exact sum required for the `n` missing rolls. Then, it checks if this sum is achievable with `n` dice (each roll between 1 and 6). If it is, it constructs a valid solution by distributing the required sum as evenly as possible among the `n` rolls.
**Time:** O(n + m) - The algorithm involves a single pass over the `rolls` array to calculate its sum (O(m)) and another pass to construct the result array of size `n` (O(n)). · **Space:** O(n) or O(1) - We need O(n) space to store and return the result array. If the output array is not considered part of the space complexity, the algorithm uses O(1) extra space.
**Pros:** Extremely efficient with linear time complexity, making it suitable for large constraints.; Simple and deterministic, directly calculating the solution without any searching.; Provides one valid solution out of potentially many, satisfying the problem requirements.
**Cons:** The logic relies on a mathematical insight, which might not be immediately obvious.; Requires careful handling of edge cases and integer arithmetic to avoid off-by-one errors.
### Explanation
The core idea is based on the definition of the mean. The total sum of all `n + m` rolls must be `mean * (n + m)`.

1.  **Calculate Missing Sum**: We first find the sum of the `m` rolls we already have. Then, we subtract this from the required total sum to find the sum needed for the `n` missing rolls. Let's call this `missingSum`.
    `missingSum = (mean * (n + m)) - sum(rolls)`

2.  **Check Feasibility**: A die roll must be an integer between 1 and 6. Therefore, the sum of `n` dice rolls must be at least `n * 1 = n` and at most `n * 6 = 6n`. If our calculated `missingSum` is outside this range `[n, 6n]`, it's impossible to find a solution, so we return an empty array.

3.  **Construct Solution**: If `missingSum` is within the valid range, a solution is guaranteed to exist. We can construct one such solution by distributing the `missingSum` as evenly as possible across the `n` rolls. We calculate a `base` value for each roll using integer division (`missingSum / n`) and a `remainder` (`missingSum % n`). This means `remainder` rolls will have a value of `base + 1`, and the other `n - remainder` rolls will have a value of `base`. Since we've already passed the feasibility check, these constructed roll values are guaranteed to be between 1 and 6.

```java
class Solution {
    public int[] missingRolls(int[] rolls, int mean, int n) {
        int m = rolls.length;
        int currentSum = 0;
        for (int roll : rolls) {
            currentSum += roll;
        }

        // Calculate the sum required for the n missing rolls
        int missingSum = mean * (n + m) - currentSum;

        // Check if this sum is possible with n dice
        if (missingSum < n || missingSum > 6 * n) {
            return new int[0];
        }

        // Distribute the missingSum among n rolls
        int[] result = new int[n];
        int baseValue = missingSum / n;
        int remainder = missingSum % n;

        for (int i = 0; i < n; i++) {
            result[i] = baseValue;
            if (remainder > 0) {
                result[i]++;
                remainder--;
            }
        }

        return result;
    }
}
```
### Algorithm
- Calculate `m`, the number of given rolls (`rolls.length`).
- Calculate `sum_m`, the sum of all elements in the `rolls` array.
- Calculate the total sum required for all `n + m` rolls to have the given `mean`: `totalSum = mean * (n + m)`.
- Determine the required sum for the `n` missing rolls: `missingSum = totalSum - sum_m`.
- Check if a solution is possible. The sum of `n` dice rolls must be between `n * 1` and `n * 6`. If `missingSum < n` or `missingSum > 6 * n`, no solution exists, so return an empty array.
- If a solution is possible, construct the result array `ans` of size `n`.
- Distribute the `missingSum` as evenly as possible. Calculate the base value for each roll: `base = missingSum / n`.
- Calculate the remainder: `rem = missingSum % n`.
- This means `rem` rolls will be `base + 1` and `n - rem` rolls will be `base`.
- Fill the `ans` array: iterate from `i = 0` to `n-1`. Set `ans[i] = base`. If `i < rem`, add 1 to `ans[i]`.
- Return the constructed `ans` array.

# Solutions
### Java

```java
class Solution {
public
  int[] missingRolls(int[] rolls, int mean, int n) {
    int m = rolls.length;
    int s = (n + m) * mean;
    for (int v : rolls) {
      s -= v;
    }
    if (s > n * 6 || s < n) {
      return new int[0];
    }
    int[] ans = new int[n];
    Arrays.fill(ans, s / n);
    for (int i = 0; i < s % n; ++i) {
      ++ans[i];
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> missingRolls(vector<int> &rolls, int mean, int n) {
    int m = rolls.size();
    int s = (n + m) * mean;
    for (int &v : rolls)
      s -= v;
    if (s > n * 6 || s < n)
      return {};
    vector<int> ans(n, s / n);
    for (int i = 0; i < s % n; ++i)
      ++ans[i];
    return ans;
  }
};

```

### Python

```python
class Solution:
    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]: m = len(rolls) s = (n + m) * mean - sum(rolls) if s > n * 6 or s < n: return [] ans = [s // n] * n for i in range(s % n): ans[i] += 1 return ans

```