#2028

Medium

LeetCode Problem Workspace

Find Missing Observations

Given a set of dice rolls, calculate the missing observations based on the mean and return them or determine if it's impossible.

array math simulation

Problem Statement

You are given a list of dice rolls and the mean of all rolls combined. Some dice rolls are missing, and your goal is to determine what values the missing rolls should have in order to achieve the given mean. If there is no valid combination, return an empty array.

You have a list of known rolls and need to calculate the missing rolls based on their count and the overall mean. If there is no valid combination of values that result in the mean, the answer should be an empty array. The challenge lies in ensuring the total sum matches the mean, which is constrained by the properties of the dice.

Examples

Example 1

Input: rolls = [3,2,4,3], mean = 4, n = 2

Output: [6,6]

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]

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: []

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

Solution Approach

Calculate Total Sum

First, compute the total sum of all rolls (the sum of both known and missing rolls) using the formula: totalSum = mean * (n + m). Subtract the sum of known rolls from this total sum to find the sum of missing rolls.

Check Validity of Missing Rolls

Next, check if it's possible to distribute the sum of missing rolls among the n missing observations such that each roll is between 1 and 6. If the sum of missing rolls exceeds the maximum possible sum (n * 6) or is less than the minimum possible sum (n * 1), return an empty array.

Return Missing Rolls

If the sum of missing rolls is valid, distribute the sum evenly among the missing rolls while ensuring no roll exceeds 6 or falls below 1. Return the calculated rolls. If no valid distribution is possible, return an empty array.

Complexity Analysis

Metric	Value
Time	O(m + n)
Space	O(1)

The time complexity is O(m + n) because we only need to iterate over the list of rolls and calculate the total sum. Space complexity is O(1) as we only need a constant amount of extra space for calculations.

What Interviewers Usually Probe

Check if the candidate can handle basic array operations and sum calculations.
Observe whether the candidate is able to handle edge cases where the mean can't be met.
Evaluate if the candidate can implement efficient validation for the missing rolls.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the constraint that each missing roll must be between 1 and 6.
Not checking if the sum of missing rolls is possible before attempting to fill the array.
Failing to return an empty array when the mean cannot be achieved.

Follow-up variants

Consider handling cases where the number of missing rolls is large, testing the efficiency of the solution.
Modify the problem to have a varying range of possible values (not just 1 to 6).
Add constraints where some rolls can be negative or fractional values, increasing the complexity.

FAQ

What is the best approach to solving Find Missing Observations?

The best approach is to first calculate the total sum of all rolls based on the given mean, then check if the missing rolls can be distributed in a way that maintains the mean.

How do I handle edge cases where the mean cannot be achieved?

You must validate if the sum of the missing rolls is feasible by ensuring it falls within the range of possible sums (between n and n*6). If not, return an empty array.

What if there are multiple valid solutions for the missing rolls?

The problem allows multiple valid solutions. Any array that meets the requirements is acceptable as a correct answer.

What topics are covered by the Find Missing Observations problem?

The problem covers array manipulation, basic math operations, and simulation techniques to calculate missing values and validate them.

How do I improve my solution for larger inputs?

For larger inputs, focus on optimizing the validation steps to avoid unnecessary checks. The solution should be efficient with respect to both time and space complexity.

terminal

Solution

Solution 1: Construction

According to the problem description, the sum of all numbers is $(n + m) \times \textit{mean}$, and the sum of known numbers is $\sum_{i=0}^{m-1} \textit{rolls}[i]$. Therefore, the sum of the missing numbers is $s = (n + m) \times \textit{mean} - \sum_{i=0}^{m-1} \textit{rolls}[i]$.

1

2

3

4

5

6

7

8

9

10

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

Continue Practicing

#2221 find triangular sum of an array #1823 find the winner of the circular game #1806 minimum number of operations to reinitialize a permutation