Find Missing Observations

2028. Find Missing Observations

Difficulty:Medium

Topics:Array, Math, Simulation

You have observations of n + m6-sideddice 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 theaverage valueof the n + m rolls.

You are given an integer array rolls of length m where rolls[i] is the value of the i^thobservation. You are also given the two integers mean and n.

Returnan 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, returnan empty array.

Theaverage valueof a set of k numbers is the sum of the numbers divided by k.

Notethat mean is an integer, so the sum of the n + mrolls 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 <= 10⁵
• 1 <= rolls[i], mean <= 6

Hint:

1. What should the sum of the n rolls be?
2. Could you generate an array of size n such that each element is between 1 and 6?

Solution:

We need to determine an array of missing rolls such that the average of all n + m dice rolls is exactly equal to mean. Here's the step-by-step breakdown of the solution:

Steps to Approach:

1. Calculate the total sum for n + m rolls:
   Given that the average value of n + m rolls is mean, the total sum of all the rolls should be total_sum = (n + m) * mean.

2. Determine the missing sum:
   The sum of the m rolls is already known. Thus, the sum of the missing n rolls should be:
   

missing_sum = total_sum - ∑(rolls)

where ∑(rolls) is the sum of the elements in the rolls array.

1. Check for feasibility:Each roll is a 6-sided die, so the missing values must be between 1 and 6 (inclusive). Therefore, the sum of the missing n rolls must be between:

min_sum = n X 1 = n

and

max_sum = n X 6 = 6n

If the missing_sum is outside this range, it's impossible to form valid missing observations, and we should return an empty array.

1. Distribute the missing sum:If missing_sum is valid, we distribute it across the n rolls by initially filling each element with 1 (the minimum possible value). Then, we increment elements from 1 to 6 until we reach the required missing_sum.

Let's implement this solution in PHP:2028. Find Missing Observations

        
Explanation:
        

         
Input:
          

           
rolls = [3, 2, 4, 3]
           
mean = 4
           
n = 2
          
         
Steps:
          

           
The total number of rolls is n + m = 6.
           
The total sum needed is 6 * 4 = 24.
           
The sum of the given rolls is 3 + 2 + 4 + 3 = 12.
           
The sum required for the missing rolls is 24 - 12 = 12.
          
        
We need two missing rolls that sum up to 12, and the only possibility is [6, 6].
        

         
Result:
          

           
For example 1: The output is [6, 6].
           
For example 2: The output is [2, 3, 2, 2].
           
For example 3: No valid solution, so the output is [].
          
        
Time Complexity:
        

         
Calculating the sum of rolls takes O(m), and distributing the missing_sum takes O(n). Hence, the overall time complexity isO(n + m), which is efficient for the input constraints.
        
This solution ensures that we either find valid missing rolls or return an empty array when no solution exists.
Contact Links
このシリーズが役立つと思われた場合は、GitHub でリポジトリにスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!
このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:
        

         
LinkedIn
         
GitHub
        
The above is the detailed content of Find Missing Observations. For more information, please follow other related articles on the PHP Chinese website!