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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Missing Observations

Difficulty: Medium

Problem Description

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.

Key Insights

  • The total number of rolls is n + m, and the required sum for these rolls can be calculated using the formula: target_sum = mean * (n + m).
  • The sum of the known rolls can be easily computed.
  • The sum of the missing rolls must then be derived as: missing_sum = target_sum - sum(rolls).
  • The missing rolls must all be between 1 and 6 inclusive.
  • We need to check if it is possible to distribute the missing_sum into n rolls such that each roll is between 1 and 6.

Space and Time Complexity

Time Complexity: O(m) - We iterate over the rolls array once to calculate the sum. Space Complexity: O(n) - We store the result in an array of size n.

Solution

To solve the problem, we first calculate the total sum required to achieve the desired mean. We then determine the sum of the existing rolls and compute the sum of the missing rolls. We check if this missing sum can be distributed into n rolls such that each roll is valid (between 1 and 6). If it can be distributed, we construct the array of missing rolls; otherwise, we return an empty array.

Code Solutions

def missingRolls(rolls, mean, n):
    m = len(rolls)
    total_rolls = n + m
    target_sum = mean * total_rolls
    sum_of_rolls = sum(rolls)
    missing_sum = target_sum - sum_of_rolls

    # Check if the missing_sum can be achieved with n rolls
    if missing_sum < n or missing_sum > 6 * n:
        return []

    # Create the result array
    result = [1] * n
    remaining = missing_sum - n

    # Distribute the remaining value to the result
    for i in range(n):
        if remaining > 0:
            add = min(5, remaining)  # maximum we can add to each roll is 5 (to make it max 6)
            result[i] += add
            remaining -= add

    return result
← Back to All Questions