LeetCode 2028 - Find Missing Observations

The problem gives us the results of some dice rolls and asks us to reconstruct the missing ones. We have a total of n + m rolls of a standard 6-sided die.

leetcodemediumarraymathsimulation

LeetCode Problem 2028

Difficulty: 🟡 Medium
Topics: Array, Math, Simulation

Solution

Problem Understanding

The problem gives us the results of some dice rolls and asks us to reconstruct the missing ones.

We have a total of n + m rolls of a standard 6-sided die. Out of those rolls:

  • m values are known and stored in the array rolls
  • n values are missing
  • the average of all n + m rolls is exactly mean

Our task is to return any valid array of length n whose values are between 1 and 6, such that the average of the complete set of rolls becomes exactly mean.

Since the average is known, we can compute the total sum that all rolls together must have.

If:

  • total number of rolls = n + m
  • desired mean = mean

then:

$$\text{required total sum} = (n + m) \times mean$$

We already know the sum of the observed rolls:

$$\text{observed sum} = \sum rolls$$

Therefore, the missing rolls must add up to:

$$\text{missing sum} = \text{required total sum} - \text{observed sum}$$

The challenge is determining whether it is possible to distribute this missing sum across exactly n dice rolls, where every value must stay within the valid dice range [1, 6].

The constraints are important:

  • 1 <= n, m <= 10^5
  • each roll value is between 1 and 6

These constraints immediately rule out exponential or brute-force search approaches. We need a linear-time solution.

Several edge cases are especially important:

  • The required missing sum may be too small. Since every die is at least 1, the minimum possible missing sum is n.
  • The required missing sum may be too large. Since every die is at most 6, the maximum possible missing sum is 6 * n.
  • The missing sum may fit within the valid range, but distributing it incorrectly could produce invalid values outside [1, 6].

The problem guarantees that if multiple valid answers exist, we may return any one of them.

Approaches

Brute Force Approach

A brute-force solution would try every possible combination of n dice rolls.

Each missing roll can take one of six values:

$$1, 2, 3, 4, 5, 6$$

So the total number of combinations is:

$$6^n$$

For every combination, we would compute the sum and check whether the average matches the required mean.

This approach is correct because it exhaustively explores every possible valid assignment of missing rolls. If a solution exists, brute force will eventually find it.

However, this method becomes completely infeasible for the given constraints. Since n can be as large as 10^5, even 6^{20} is already astronomically large, making exhaustive search impossible.

Optimal Approach

The key observation is that we do not actually care about the exact arrangement of values, only whether the required sum can be distributed across n dice.

Instead of searching through combinations, we can directly construct a valid answer.

First, compute the total missing sum:

$$\text{missing sum} = (n + m) \times mean - \sum rolls$$

Now we check feasibility:

  • minimum possible sum with n dice = n
  • maximum possible sum with n dice = 6n

If the missing sum falls outside this range, no solution exists.

Otherwise, we can construct the answer greedily.

One simple strategy is:

  • start every missing roll at 1
  • this uses a base sum of n
  • distribute the remaining amount across the dice
  • each die can receive at most 5 extra points, since the maximum value is 6

This guarantees that all values remain valid.

Because we only traverse the array once, the solution runs in linear time.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(6^n) O(n) Tries every possible combination of missing rolls
Optimal O(n + m) O(n) Computes required sum directly and constructs a valid distribution

Algorithm Walkthrough

  1. Compute the sum of the observed rolls.

We first calculate:

observed_sum = sum(rolls)

This tells us how much contribution already exists from the known dice rolls. 2. Compute the required total sum.

Since the average of all rolls must equal mean:

total_sum = (n + len(rolls)) * mean
  1. Compute the missing sum.

The missing rolls together must contribute:

missing_sum = total_sum - observed_sum
  1. Check whether the missing sum is feasible.

Every missing die must be between 1 and 6.

Therefore:

  • minimum possible missing sum = n
  • maximum possible missing sum = 6 * n

If:

missing_sum < n

or

missing_sum > 6 * n

then no valid solution exists, so we return an empty array. 5. Initialize all missing rolls to 1.

This guarantees all values are valid and gives us the minimum possible sum:

result = [1] * n
  1. Compute how much extra sum still needs to be distributed.

Since we already assigned 1 to every position:

remaining = missing_sum - n
  1. Distribute the remaining sum greedily.

Traverse the array and add as much as possible to each die.

Each die can receive at most 5 additional points because:

current value = 1
maximum value = 6

So:

add = min(5, remaining)

Then:

result[i] += add
remaining -= add
  1. Return the constructed array.

Once the remaining amount becomes zero, the array satisfies all constraints.

Why it works

The algorithm works because it constructs values while always maintaining valid dice bounds.

Starting with all ones guarantees the minimum feasible configuration. The remaining sum represents additional value that must be distributed. Since each die can increase by at most five more points, distributing greedily never violates the upper bound of six.

The feasibility check guarantees that the required sum lies within the achievable range. Therefore, if the check passes, the greedy construction will always succeed.

Python Solution

from typing import List

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

        missing_sum = required_total - observed_sum

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

        result = [1] * n
        remaining = missing_sum - n

        for i in range(n):
            if remaining == 0:
                break

            extra = min(5, remaining)
            result[i] += extra
            remaining -= extra

        return result

The implementation directly follows the algorithm described earlier.

First, we compute the observed sum using Python's built-in sum() function. Then we calculate the total required sum based on the desired mean.

The variable missing_sum represents how much total value the missing dice must contribute.

The feasibility check is critical. If the missing sum is smaller than n, even assigning all dice as 1 would exceed the target. If the missing sum is larger than 6 * n, even assigning all dice as 6 would not be enough.

After confirming feasibility, the code initializes every missing die to 1. This guarantees all values are valid from the beginning.

The remaining amount is then distributed greedily. Each die can absorb at most 5 additional points before reaching the maximum value of 6.

The loop stops early once all remaining value has been distributed.

Go Solution

func missingRolls(rolls []int, mean int, n int) []int {
    observedSum := 0
    for _, value := range rolls {
        observedSum += value
    }

    totalRolls := len(rolls) + n
    requiredTotal := totalRolls * mean

    missingSum := requiredTotal - observedSum

    if missingSum < n || missingSum > 6*n {
        return []int{}
    }

    result := make([]int, n)

    for i := 0; i < n; i++ {
        result[i] = 1
    }

    remaining := missingSum - n

    for i := 0; i < n && remaining > 0; i++ {
        extra := remaining
        if extra > 5 {
            extra = 5
        }

        result[i] += extra
        remaining -= extra
    }

    return result
}

The Go implementation follows the same logic as the Python version.

One small difference is that Go requires explicit initialization of slices. We create the result slice using make([]int, n) and manually assign each element to 1.

When no solution exists, the function returns an empty slice []int{}.

Integer overflow is not a concern because the maximum possible total sum is:

$$(10^5 + 10^5) \times 6 = 1.2 \times 10^6$$

which safely fits inside Go's integer type.

Worked Examples

Example 1

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

Step 1: Compute observed sum

Rolls Sum
[3,2,4,3] 12

Step 2: Compute required total sum

total rolls = 4 + 2 = 6
required total = 6 * 4 = 24

Step 3: Compute missing sum

missing sum = 24 - 12 = 12

Step 4: Feasibility check

minimum possible = 2
maximum possible = 12

Since 12 is within [2, 12], a solution exists.

Step 5: Initialize result

result = [1, 1]
remaining = 12 - 2 = 10

Step 6: Distribute remaining

Index Add Result Remaining
0 5 [6,1] 5
1 5 [6,6] 0

Final answer:

[6,6]

Example 2

Input:
rolls = [1,5,6]
mean = 3
n = 4

Step 1: Compute observed sum

1 + 5 + 6 = 12

Step 2: Compute required total

total rolls = 3 + 4 = 7
required total = 7 * 3 = 21

Step 3: Compute missing sum

missing sum = 21 - 12 = 9

Step 4: Feasibility check

minimum possible = 4
maximum possible = 24

Valid.

Step 5: Initialize

result = [1,1,1,1]
remaining = 9 - 4 = 5

Step 6: Distribute remaining

Index Add Result Remaining
0 5 [6,1,1,1] 0

Final answer:

[6,1,1,1]

This differs from the sample output, but it is still valid because any valid solution is accepted.

Example 3

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

Step 1: Compute observed sum

1 + 2 + 3 + 4 = 10

Step 2: Compute required total

total rolls = 8
required total = 8 * 6 = 48

Step 3: Compute missing sum

missing sum = 48 - 10 = 38

Step 4: Feasibility check

maximum possible with 4 dice = 24

Since 38 > 24, no solution exists.

Return:

[]

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) We sum the existing rolls once and traverse the result array once
Space O(n) The output array stores n missing values

The algorithm performs only simple arithmetic and linear traversals. No nested loops or expensive data structures are used. Since constructing the answer itself requires storing n values, O(n) auxiliary space is unavoidable.

Test Cases

from typing import List

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

        missing_sum = required_total - observed_sum

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

        result = [1] * n
        remaining = missing_sum - n

        for i in range(n):
            if remaining == 0:
                break

            extra = min(5, remaining)
            result[i] += extra
            remaining -= extra

        return result

sol = Solution()

# Provided example 1
assert sorted(sol.missingRolls([3,2,4,3], 4, 2)) == [6,6]

# Provided example 2
result = sol.missingRolls([1,5,6], 3, 4)
assert len(result) == 4
assert sum(result) + sum([1,5,6]) == 21

# Provided example 3
assert sol.missingRolls([1,2,3,4], 6, 4) == []

# Minimum valid values
assert sol.missingRolls([1], 1, 1) == [1]

# Maximum valid values
assert sol.missingRolls([6], 6, 1) == [6]

# Impossible because sum too small
assert sol.missingRolls([6,6], 1, 2) == []

# Impossible because sum too large
assert sol.missingRolls([1,1], 6, 2) == []

# Single missing roll
assert sol.missingRolls([3,3,3], 3, 1) == [3]

# Large n stress test
result = sol.missingRolls([3] * 100000, 3, 100000)
assert len(result) == 100000
assert all(1 <= x <= 6 for x in result)

# Distribution requiring mixed values
result = sol.missingRolls([2,2,2], 4, 3)
assert len(result) == 3
assert sum(result) + 6 == 24

Test Summary

Test Why
Example 1 Verifies a case where all missing dice become maximum values
Example 2 Verifies general valid distribution
Example 3 Verifies impossible large sum case
[1], mean=1, n=1 Tests smallest valid input
[6], mean=6, n=1 Tests largest single-die values
Impossible small sum Ensures lower-bound feasibility check works
Impossible large sum Ensures upper-bound feasibility check works
Single missing roll Tests simplest reconstruction
Large stress test Verifies linear performance
Mixed distribution case Ensures correct sum distribution

Edge Cases

One important edge case occurs when the missing sum is smaller than n. Since every die must be at least 1, the smallest possible total for n dice is exactly n. Any smaller target sum is impossible. A naive implementation that skips this feasibility check could accidentally produce zeros or negative values.

Another important edge case occurs when the missing sum exceeds 6 * n. Even if every missing die equals 6, the total would still be too small. Without this validation step, an implementation might incorrectly generate values larger than 6, violating the problem constraints.

A third important edge case involves large input sizes near 10^5. Recursive or brute-force approaches would fail either due to time complexity or stack limitations. The implemented solution avoids recursion entirely and processes the data with only linear traversals, making it efficient even at maximum constraints.

A subtle edge case appears when the remaining extra sum becomes zero before reaching the end of the array. In this situation, the remaining dice should stay at 1. The implementation handles this naturally because all positions start at 1, and the loop exits early once no additional value needs to be distributed.