Problem Description

You are given information about dice rolls where some observations are missing. Here's the scenario:

• You originally had n + m dice rolls (using standard 6-sided dice with faces numbered 1 to 6)
• You lost the records of n rolls and only have m rolls remaining
• You know the average value of all n + m rolls

Given:

• An array rolls of length m containing the values of the known dice rolls
• An integer mean representing the average of all n + m rolls
• An integer n representing the number of missing rolls

Your task is to find the n missing dice roll values such that when combined with the known m rolls, the average equals exactly mean.

Key constraints:

• Each die shows a value between 1 and 6 (inclusive)
• The average is calculated as the sum of all values divided by the total count
• Since mean is an integer, the total sum must be divisible by n + m
• If multiple valid answers exist, return any one of them
• If no valid answer exists, return an empty array

For example, if you have 3 known rolls [3, 2, 4] with mean = 4 and n = 2 missing rolls, you need to find 2 values (each between 1-6) such that the average of all 5 rolls equals 4. This means the total sum should be 5 × 4 = 20. Since the known rolls sum to 9, the missing rolls must sum to 11, which could be [5, 6] or [6, 5].

Intuition

The key insight is to work backwards from the given average to find what the missing rolls must sum to.

Since we know the average of all n + m rolls is mean, we can calculate the total sum of all rolls: total_sum = (n + m) × mean.

We already have m rolls, so we can find their sum. The difference between the total sum and the known sum tells us exactly what the n missing rolls must add up to: missing_sum = total_sum - sum(known_rolls).

Now we need to check if it's possible to create n dice rolls that sum to missing_sum. Each die can show values from 1 to 6, so:

• The minimum possible sum for n dice is n × 1 = n
• The maximum possible sum for n dice is n × 6

If missing_sum falls outside the range [n, n × 6], it's impossible to achieve, so we return an empty array.

If it's possible, we need to distribute missing_sum across n dice. The simplest approach is to distribute as evenly as possible:

• Start by giving each die the value missing_sum // n (integer division)
• This leaves a remainder of missing_sum % n
• Distribute this remainder by adding 1 to the first missing_sum % n dice

This greedy distribution works because:

• We're guaranteed each die value stays within [1, 6] since we already checked the sum is achievable
• It's the most straightforward way to construct a valid answer
• Any valid distribution will work according to the problem statement

Learn more about Math patterns.

Solution Approach

The implementation follows the mathematical approach we identified:

1. Calculate the required sum for missing rolls:

   • First, find the total sum needed: total_sum = (n + m) × mean
   • Calculate the sum of known rolls: known_sum = sum(rolls)
   • The missing rolls must sum to: s = total_sum - known_sum

2. Check if a valid solution exists:

   • Since each die shows values from 1 to 6, the sum s must satisfy: n ≤ s ≤ n × 6
   • If s < n (less than minimum possible) or s > n × 6 (more than maximum possible), return an empty array

3. Construct the missing rolls using even distribution:

   • Initialize all n missing rolls with the base value: s // n
   • This uses up n × (s // n) from our required sum
   • We still need to distribute the remainder: s % n
   • Add 1 to the first s % n dice to distribute the remainder

Here's how the algorithm works step by step:

m = len(rolls)                           # Get number of known rolls
s = (n + m) * mean - sum(rolls)          # Calculate required sum for missing rolls

if s > n * 6 or s < n:                   # Check if solution is possible
    return []

ans = [s // n] * n                       # Initialize all dice with base value
for i in range(s % n):                   # Distribute remainder
    ans[i] += 1
  
return ans

This approach guarantees:

• All dice values remain within [1, 6] range
• The sum of missing rolls equals exactly s
• The solution is constructed in O(n) time with O(n) space

For example, if we need n = 3 missing rolls that sum to s = 11:

• Base value: 11 // 3 = 3, so start with [3, 3, 3]
• Remainder: 11 % 3 = 2, so add 1 to first 2 elements
• Final result: [4, 4, 3]

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• Known rolls: rolls = [1, 5, 6] (m = 3 rolls)
• Mean of all rolls: mean = 3
• Missing rolls: n = 4

Step 1: Calculate the required sum for missing rolls

First, we need to find what the missing rolls must sum to:

• Total number of rolls: n + m = 4 + 3 = 7
• Total sum needed: total_sum = 7 × 3 = 21
• Sum of known rolls: sum([1, 5, 6]) = 12
• Required sum for missing rolls: s = 21 - 12 = 9

So our 4 missing dice must sum to exactly 9.

Step 2: Check if a valid solution exists

Can we create 4 dice rolls that sum to 9?

• Minimum possible sum: 4 × 1 = 4 (all dice show 1)
• Maximum possible sum: 4 × 6 = 24 (all dice show 6)
• Our required sum s = 9 falls within the range [4, 24] ✓

Since 4 ≤ 9 ≤ 24, a valid solution exists!

Step 3: Construct the missing rolls

Now we distribute the sum of 9 across 4 dice:

• Base value for each die: 9 // 4 = 2
• Start with: [2, 2, 2, 2] (sum = 8)
• Remainder to distribute: 9 % 4 = 1
• Add 1 to the first die: [3, 2, 2, 2] (sum = 9) ✓

Verification:

• All 7 rolls: [1, 5, 6, 3, 2, 2, 2]
• Total sum: 1 + 5 + 6 + 3 + 2 + 2 + 2 = 21
• Average: 21 / 7 = 3 ✓
• All dice values are between 1 and 6 ✓

The answer [3, 2, 2, 2] satisfies all requirements!

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m)

The time complexity consists of:

• O(m) for calculating sum(rolls) where m is the length of the given rolls array
• O(n) for creating the initial answer array with [s // n] * n
• O(s % n) for the loop that distributes the remainder, where s % n < n, so this is O(n) in the worst case

Therefore, the overall time complexity is O(m) + O(n) + O(n) = O(n + m).

Space Complexity: O(1) (excluding the output array)

The algorithm uses only a constant amount of extra space:

• Variables m, s, and loop variable i each require O(1) space
• The answer array ans of size n is required for the output and is not counted in the space complexity analysis

If we were to include the output array, the space complexity would be O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in Sum Calculation

When calculating (n + m) * mean, this multiplication can cause integer overflow for large values. In some languages like C++ or Java, this would result in incorrect calculations.

Problem Example:

# If n + m = 100000 and mean = 60000
# (n + m) * mean = 6,000,000,000 (exceeds 32-bit integer limit)

Solution:

• Use 64-bit integers or long data types in languages prone to overflow
• In Python, this isn't an issue due to arbitrary precision integers
• Alternative calculation order: n * mean + m * mean to reduce intermediate values

2. Incorrect Remainder Distribution

A common mistake is trying to distribute the remainder incorrectly, potentially creating invalid die values.

Problem Example:

# Wrong approach:
result = [s // n] * n
result[0] += s % n  # Adding all remainder to one die - might exceed 6!

# If s = 14, n = 3: base = 4, remainder = 2
# Wrong result: [6, 4, 4] ✓ (happens to work)
# But if s = 17, n = 3: base = 5, remainder = 2  
# Wrong result: [7, 5, 5] ✗ (7 is invalid!)

Solution: Distribute remainder by adding 1 to multiple dice:

for i in range(s % n):
    result[i] += 1  # Add 1 to each of the first (s % n) dice

3. Forgetting Edge Case Validation

Not checking if the base value itself is valid (between 1 and 6).

Problem Example:

# If s = 21, n = 3: base = 7 (invalid even before remainder distribution)
# If s = 2, n = 3: base = 0 (invalid, dice can't show 0)

Solution: The validation if s > n * 6 or s < n: handles this implicitly:

• If base value would be > 6, then s > n * 6
• If base value would be < 1, then s < n

4. Off-by-One Error in Validation

Using incorrect inequality operators in the validation check.

Problem Example:

# Wrong validation:
if s >= n * 6 or s <= n:  # Using >= and <= instead of > and <
    return []

# This would incorrectly reject valid cases:
# s = 6, n = 1 (all 6s) would be rejected
# s = 3, n = 3 (all 1s) would be rejected

Solution: Use strict inequalities for the impossible cases:

if s > n * 6 or s < n:  # Correct validation
    return []

5. Not Handling Zero or Negative Missing Sum

Failing to handle cases where the known rolls already exceed or meet the required average.

Problem Example:

# rolls = [6, 6, 6], mean = 3, n = 2
# missing_sum = 5 * 3 - 18 = -3 (negative!)

Solution: The validation if s < n: catches this since negative numbers are less than any positive n.