{x}
blog image

Find Missing Observations

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

Problem Description

The problem asks to find missing observations from a set of dice rolls given the mean of all rolls (including the missing ones) and the number of missing rolls. The dice have 6 sides (1-6). If a solution exists, return an array of the missing observations; otherwise, return an empty array.

Solution Approach

The core idea is to utilize the relationship between the total sum of rolls, the mean, and the number of rolls.

  1. Calculate the total sum: The total sum of all rolls (both known and missing) is calculated as (n + m) * mean, where n is the number of missing rolls, m is the number of known rolls, and mean is the given average.

  2. Calculate the sum of missing rolls: Subtract the sum of the known rolls (from the rolls array) from the total sum calculated in step 1. This gives the sum of the missing rolls.

  3. Check for feasibility: If the sum of missing rolls is greater than the maximum possible sum ( n * 6 ) or less than the minimum possible sum (n), it's impossible to find a valid solution. Return an empty array in this case.

  4. Distribute the sum: If a solution is possible, distribute the sum of missing rolls as evenly as possible among the n missing rolls. Integer division (s // n) gives the base value for each missing roll. The remainder (s % n) represents the number of rolls that need to be incremented by 1 to reach the exact sum.

  5. Construct and return the result: Create an array of size n and fill it with the base value. Then, increment the first s % n elements by 1 to account for the remainder.

Time and Space Complexity

  • Time Complexity: O(m + n), dominated by the calculation of the sum of known rolls and the construction of the result array. m is length of rolls and n is the number of missing rolls.

  • Space Complexity: O(n). The space used is primarily for the resulting array of missing rolls. The other variables used have constant space complexity.

Code Implementation (Python)

class Solution:
    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:
        m = len(rolls)
        total_sum = (n + m) * mean
        known_sum = sum(rolls)
        missing_sum = total_sum - known_sum
 
        if missing_sum > n * 6 or missing_sum < n:
            return []
 
        base_value = missing_sum // n
        remainder = missing_sum % n
        result = [base_value] * n
        for i in range(remainder):
            result[i] += 1
        return result

The code in other languages (Java, C++, Go, TypeScript, Rust) follows the same logic and algorithmic steps, differing only in syntax and specific library functions used. The core idea remains consistent across all implementations.