Find Missing Observations

Leetcode Problem:

• Find Missing Observations

Summary

• Find the missing 6-sided dice rolls to achieve a given average value.

Approach

• This solution calculates the total sum of all rolls by multiplying the mean by the total number of rolls
• It then subtracts the sum of the known rolls from the total sum to find the sum of the missing rolls
• The solution then iterates through the missing rolls, assigning the average value to each roll and adjusting the value if necessary to ensure the total sum is divisible by the total number of rolls.

Complexity

• O(n)

Explain

• The time complexity of this solution is O(n) because it iterates through the missing rolls once
• The space complexity is O(n) because it stores the missing rolls in a vector.

Solution Code:

class Solution {
public:
    vector missingRolls(vector& rolls, int mean, int n) {
        vector ans;
        int m = rolls.size();
        int totalSum = (m + n) * mean;
        for(int i = 0 ; i < m; i++){
            totalSum -= rolls[i];
        }
        if(totalSum < n || totalSum > n*6) return ans;
        for(int i = 0 ; i < n; i++){
            ans.push_back(totalSum/n);
            if (totalSum % n != 0){
                ans[i] += 1;
                totalSum--;
            }
        }
        return ans;
    }
};