We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Missing Observations

Number: 2155

Difficulty: Medium

Paid? No

Companies: Microsoft, Bloomberg, ASUS, Amazon

Problem Description

Given an array of m observed dice rolls and the mean of all n + m dice rolls, determine the n missing dice roll observations (each between 1 and 6) such that the overall mean is exactly the given mean. If there is no valid distribution of missing dice rolls that can achieve the target mean, return an empty array.

Key Insights

  • Calculate the total sum needed from all n + m dice rolls using the mean.
  • Determine the sum of the missing n observations by subtracting the sum of the observed rolls from the total required sum.
  • Check if the missing sum is feasible given that each missing observation can only be between 1 and 6.
  • If feasible, distribute the extra sum (above the minimum possible) evenly across the n observations without exceeding the maximum possible value for a dice roll.
  • Return the resulting list of missing observations.

Space and Time Complexity

Time Complexity: O(n + m) – We iterate through the observed rolls to sum them and then iterate through the n missing observations. Space Complexity: O(n) – We store the n missing observations in a list.

Solution

To solve the problem:

  1. Compute the total sum required for all n + m observations: totalRequired = mean * (n + m).
  2. Calculate the observed sum from the given rolls.
  3. The sum missing = totalRequired - observedSum must be distributed among n dice rolls.
  4. Check if this missing sum is within the possible bounds: it must be at least n (if all dice show 1) and at most 6*n (if all dice show 6). If not, return an empty array.
  5. Initialize each missing observation with the minimum value 1, then compute the additional sum needed (extraSum = missingSum - n).
  6. Distribute the extra sum: For each missing observation, add up to 5 (maximum increase from 1 to 6) or the remaining extraSum until it is exhausted.
  7. Return the resulting list of missing observations.

Code Solutions

# Python solution for finding missing observations.
def missingRolls(rolls, mean, n):
    # Calculate the total required sum for all dice rolls.
    m = len(rolls)
    total_required = mean * (n + m)
    
    # Sum of observed dice rolls.
    observed_sum = sum(rolls)
    
    # Calculate the sum that needs to be distributed among the missing rolls.
    missing_sum = total_required - observed_sum
    
    # Check if missing_sum can be distributed across n rolls such that each is in [1,6].
    if missing_sum < n or missing_sum > 6 * n:
        # Return an empty array if the distribution is impossible.
        return []
    
    # Initialize the answer array with each roll as 1.
    answer = [1] * n
    # Extra sum to distribute after setting each roll to its minimum.
    extra = missing_sum - n
    
    # Distribute the extra sum among the missing rolls.
    for i in range(n):
        # Determine how much extra can be added to this turn, maximum is 5.
        add = min(5, extra)
        answer[i] += add
        extra -= add
        # Break early if no extra remains.
        if extra == 0:
            break
    return answer

# Example usage:
print(missingRolls([3, 2, 4, 3], 4, 2))  # Expected output: [6, 6]
← Back to All Questions