Find Missing Observations

Med

#1846Time: 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.

Patterns

Math

Data structures

Array

Prompt

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 i^th 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 <= 10⁵
1 <= rolls[i], mean <= 6

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    private int[] result;3    private int n_val;4    private int targetSum;5 6    public int[] missingRolls(int[] rolls, int mean, int n) {7        this.n_val = n;8        int m = rolls.length;9        int sum_m = 0;10        for (int roll : rolls) {11            sum_m += roll;12        }13 14        this.targetSum = mean * (n + m) - sum_m;15 16        if (targetSum < n || targetSum > 6 * n) {17            return new int[0];18        }19 20        this.result = null;21        findCombination(0, 0, new int[n]);22        return result == null ? new int[0] : result;23    }24 25    private boolean findCombination(int k, int currentSum, int[] combination) {26        if (k == n_val) {27            if (currentSum == targetSum) {28                this.result = combination.clone();29                return true;30            }31            return false;32        }33 34        // Pruning35        if (currentSum + (n_val - k) * 1 > targetSum || currentSum + (n_val - k) * 6 < targetSum) {36            return false;37        }38 39        for (int v = 1; v <= 6; v++) {40            combination[k] = v;41            if (findCombination(k + 1, currentSum + v, combination)) {42                return true;43            }44        }45        return false;46    }47}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

The core idea is based on the definition of the mean. The total sum of all n + m rolls must be mean * (n + m).

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)
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.
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.

1class Solution {2    public int[] missingRolls(int[] rolls, int mean, int n) {3        int m = rolls.length;4        int currentSum = 0;5        for (int roll : rolls) {6            currentSum += roll;7        }8 9        // Calculate the sum required for the n missing rolls10        int missingSum = mean * (n + m) - currentSum;11 12        // Check if this sum is possible with n dice13        if (missingSum < n || missingSum > 6 * n) {14            return new int[0];15        }16 17        // Distribute the missingSum among n rolls18        int[] result = new int[n];19        int baseValue = missingSum / n;20        int remainder = missingSum % n;21 22        for (int i = 0; i < n; i++) {23            result[i] = baseValue;24            if (remainder > 0) {25                result[i]++;26                remainder--;27            }28        }29 30        return result;31    }32}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int[] missingRolls(int[] rolls, int mean, int n) {4    int m = rolls.length;5    int s = (n + m) * mean;6    for (int v : rolls) {7      s -= v;8    }9    if (s > n * 6 || s < n) {10      return new int[0];11    }12    int[] ans = new int[n];13    Arrays.fill(ans, s / n);14    for (int i = 0; i < s % n; ++i) {15      ++ans[i];16    }17    return ans;18  }19}

1class Solution {2public:3  vector<int> missingRolls(vector<int> &rolls, int mean, int n) {4    int m = rolls.size();5    int s = (n + m) * mean;6    for (int &v : rolls)7      s -= v;8    if (s > n * 6 || s < n)9      return {};10    vector<int> ans(n, s / n);11    for (int i = 0; i < s % n; ++i)12      ++ans[i];13    return ans;14  }15};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem