2028. 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

Approach 01:

class Solution {
public:
    vector<int> missingRolls(vector<int>& rolls, int mean, int n) {
        const int targetSum = (rolls.size() + n) * mean;
        int missingSum = targetSum - accumulate(rolls.begin(), rolls.end(), 0);
        if (missingSum > n * 6 || missingSum < n){
            return {};
        }

        vector<int> result(n, missingSum / n);
        missingSum %= n;
        for (int i = 0; i < missingSum; ++i){
            ++result[i];
        }
        return result;
    }
};

class Solution:
    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:
        targetSum = (len(rolls) + n)*mean
        missingSum = targetSum - sum(rolls)

        if(missingSum > (n*6) or missingSum < n):
            return []
        
        result = [missingSum//n]*n
        missingSum %= n

        for i in range(missingSum):
            result[i] += 1
        return result

Time Complexity

• Calculating the Target Sum:

  The operation to compute targetSum takes \( O(1) \) time since it involves only basic arithmetic operations.

• Calculating the Sum of the Existing Rolls:

  The function accumulate is used to calculate the sum of all elements in the input vector rolls. This takes \( O(m) \) time, where m is the size of the input vector rolls.

• Constructing the Result Vector:

  The initialization of the vector result takes \( O(n) \) time, where n is the size of the vector result. The subsequent loop that adjusts the values also takes \( O(n) \) time.

• Overall Time Complexity:

  The overall time complexity is \( O(m + n) \), where m is the size of rolls and n is the number of missing dice rolls to be computed.

Space Complexity

• Space for the Result Vector:

  The vector result of size n is created to store the missing dice rolls, which takes \( O(n) \) space.

• Space for Variables:

  Only a few additional integer variables (like targetSum, missingSum, and loop counters) are used, which takes \( O(1) \) space.

• Overall Space Complexity:

  The overall space complexity is \( O(n) \) due to the space required for the result vector.