2028. Find Missing Observations

Problem Description

You are given a certain amount of 6-sided dice roll observations m, but unfortunately, n additional observations are missing. The average value of all n + m dice rolls, including the missing ones, has been calculated and is known to you. It is your task to reconstruct the missing n observations such that when combined with the provided m observations, the overall average remains the same.

The known m observations are provided in an array called rolls, the overall average (which is an integer) is given by mean, and the number of missing observations is n.

Your goal is to return an array of length n that represents the missing observations. The constraints you must abide by are:

• The sum of the resulting n + m observations must be equal to mean * (n + m) since that product gives the total sum implied by the average mean.
• Each element in the resulting array must be a valid dice roll number between 1 and 6.

If it's impossible to find such an array that satisfies these conditions, you are to return an empty array instead.

Intuition

Understanding this problem requires recognizing that it's a matter of distributing a specific sum (s) across n rolls such that each roll is between 1 and 6.

Since the problem states that the average is an integer, we know the total sum of all observations must be divisible by the number of observations, which is a key starting point. Moreover, we are dealing with average values, meaning the total sum must be spread over can be determined by the formula (n + m) * mean.

Here's how we arrive at the solution approach:

1. Calculate the total sum s needed for the missing observations by subtracting the sum of given rolls from the desired total sum. This gives us the amount that the missing rolls must sum up to.
2. Confirm that it's possible to construct a valid array with the missing observations:
   • The minimum sum we could get from n dice rolls is n, with each roll being 1.
   • The maximum sum we could get from n dice rolls is 6 * n, with each roll being 6.
   • So, if s is outside of the range [n, 6 * n], constructing an array is impossible, and we should return an empty list.
3. If the sum s falls within the valid range, we distribute it evenly across the n missing observations. Each missing observation will initially be assigned the integer part of the division s // n.
4. However, since s may not be exactly divisible by n, there could be a remainder. This remainder has to be distributed amongst the observations as well. We do this by adding 1 to each of the first s % n observations since the remainder can be at most n-1.
5. After these steps, we would have an array that contains the missing observations and satisfies the average value requirement.

The approach used in the Python code above implements these steps succinctly, ensuring that all constraints of the problem are met.

Learn more about Math patterns.

Solution Approach

The implementation follows a direct approach, which aligns with the intuition previously explained.

To outline the steps of the implementation:

1. Calculate the sum s that the missing rolls must add up to. This is done by multiplying the overall mean by the total number of observations (both missing and known), and then subtracting the sum of the known observations:

   1s = (n + m) * mean - sum(rolls)

   m is the number of known observations, so len(rolls) gives us this value.

2. Check if the sum s is within the bounds of what is achievable with n rolls. The conditions for s to be valid are that it can't be less than n (since every roll is at least 1) and it can't be greater than 6 * n (since every roll is at most 6):

   1if s > n * 6 or s < n:
   2    return []

   If s does not satisfy these conditions, an empty list is returned, signaling that it's impossible to have such a distribution.

3. Allocate the minimum guaranteed value to each of the n missing observations by performing integer division of s by n. This ensures that we are using up as much of s as possible while keeping the value of each roll within the dice's constraints (1 - 6 inclusive).

   1ans = [s // n] * n

   Here, ans is the list that will be returned, initially filled with the integer part of the division.

4. Distribute the remainder of s across the n missing observations. The modulus operator % gives the remainder of the division between s and n:

   1for i in range(s % n):
   2    ans[i] += 1

   We only need to iterate over the first s % n elements of the ans array. This ensures that the extra values are as evenly distributed as possible without exceeding the die's face value limit of 6.

This approach assumes that there are valid values for all missing observations such that their sum is s. By using integer division and modular arithmetic, the solution fills the ans array with valid die rolls that reach the sum s without violating any of the dice constraints. The algorithm has a constant time complexity with respect to the input array rolls since it's only dependent on the number of missing observations n. The space complexity is also linear with respect to the number of missing observations n.

Example Walkthrough

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

Suppose we are given the following parameters:

• rolls: [3, 4, 3] representing the known dice rolls
• mean: 4 as the overall average of all the dice rolls (including the missing ones).
• n: 2 indicating that there are two missing observations.

We want to reconstruct the missing observations such that the resulting array, when combined with the provided observations, results in the average value 4.

Following the steps outlined in the solution approach:

1. Calculate the total sum s needed for the missing observations:

   First, we determine the total number of observations (missing + known), which is 3 + 2 = 5.

   Then, we calculate the total sum implied by the average:

   1s = (n + m) * mean - sum(rolls)
   2s = (2 + 3) * 4 - sum([3, 4, 3])
   3s = 5 * 4 - 10
   4s = 20 - 10
   5s = 10

   So, the sum of the two missing observations must be 10.

2. Check if the sum s is within the achievable bounds:

   We must check if s is at least n (every roll is at least 1) and at most 6 * n (every roll is at most 6):

   Since s is 10, which is within the range of [2, 12] ([n, 6 * n]), there is a possible solution.

3. Allocate the minimum guaranteed value to each missing observation:

   We divide the sum s by the number of missing observations n:

   1ans = [s // n] * n
   2ans = [10 // 2] * 2
   3ans = [5] * 2
   4ans = [5, 5]

   This provides us with an initial distribution for the missing observations.

4. Distribute the remainder of s across the missing observations:

   Since s is exactly divisible by n in this case, there is no remainder and this step is not necessary. The distribution [5, 5] already satisfies the conditions since both numbers are between 1 and 6 and the total is 10.

Thus, the reconstructed array [5, 5] when combined with the original rolls [3, 4, 3], maintains the average value 4:

• Total value of all rolls: 3 + 4 + 3 + 5 + 5 = 20
• Number of all rolls: 5
• Average (Total value / Number of rolls): 20 / 5 = 4

Therefore, the final reconstructed array with the missing observations would be [5, 5]. This completes the example walkthrough using the given approach.

Solution Implementation

Time and Space Complexity

The time complexity of the provided code is O(m), where m is the number of elements in the rolls list. This time complexity comes from the need to calculate the sum of the rolls list with the sum(rolls) function. The rest of the operations, including the division and modulus operations, as well as assigning values to the ans list, have a constant time complexity or a time complexity of O(n) which is dominated by the O(m) complexity due to the summing operation, assuming n is much smaller than or at most equal to m.

The space complexity is O(n), because we are creating a list ans which contains n integers. The space taken up by m is negligible compared to n because we are given that we're generating n new roll results, and no other data structures are utilized that are dependent on the size of the input.

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