Problem

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.

Examples

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.

Solution

Method 1 - Using maths and distributing 1 and max 6

  1. Calculate Total Required Sum:
    • The total number of rolls is ( n + m ).
    • The required total sum to achieve the given mean is mean * (n+m)
  2. Sum of Given Rolls:
    • Compute the sum of the given ( m ) dice rolls.
  3. Determine Remaining Sum:
    • Compute the remaining sum that needs to be distributed among the ( n ) missing rolls: missingSum = totalSum - currSum.
  4. Check Feasibility:
    • Ensure that the remaining sum can be evenly distributed such that each missing roll is between 1 and 6.
    • This implies: n <= missingSum <= 6n
  5. Construct the Missing Rolls:
    • Start with an array of ( n ) elements, each initialized to 1.
    • Distribute the remaining sum amongst these elements without exceeding the maximum roll value of 6.

Here is the short calculation:

currSum = sum(rolls)
totalSum / (n + m) == mean
totalSum = mean * (n+m)
totalSum = currSum + missingSum
missingSum = totalSum - currSum = mean * (n+m) - currSum

Video Explanation

Here is the video explanation of same:

Code

Java
Distribute 1 initially and 5 later on
public class Solution {
    public int[] missingRolls(int[] rolls, int mean, int n) {
        int m = rolls.length;
        // Calculate the total sum required for n + m rolls to have the given
        // mean
        int totalSum = mean * (n + m);
        // Calculate the current sum of the observed rolls
        int currSum = Arrays.stream(rolls).sum();
        // Calculate the sum needed from the missing n rolls
        int missingSum = totalSum - currSum;

        // Check if it is possible to split missingSum into n parts with each
        // part between 1 and 6
        if (missingSum < n || missingSum > 6 * n) {
            return new int[0]; // Return an empty array if not possible
        }

        // Construct the result
        int[] ans = new int[n];
        Arrays.fill(ans, 1);
        missingSum -= n; // We have initially assigned each part as 1

        for (int i = 0; i < n; i++) {
            if (missingSum > 0) {
                int add = Math.min(5, missingSum); // We can add at most 5 more to each part
                ans[i] += add;
                missingSum -= add;
            }
        }

        return ans;
    }
}
Distribute missingSum by n initially and remaining later
public class Solution {
    public int[] missingRolls(int[] rolls, int mean, int n) {
        int m = rolls.length;
        // Calculate the total sum required for n + m rolls to have the given
        // mean
        int totalSum = mean * (n + m);
        // Calculate the current sum of the observed rolls
        int currSum = Arrays.stream(rolls).sum();
        // Calculate the sum needed from the missing n rolls
        int missingSum = totalSum - currSum;

        // Check if it is possible to split missingSum into n parts with each
        // part between 1 and 6
        if (missingSum < n || missingSum > 6 * n) {
            return new int[0]; // Return an empty array if not possible
        }

        // Construct the result
        int[] ans = new int[n];
        int initialPart = missingSum / n, remaining = missingSum % n;
        Arrays.fill(ans, initialPart);
        
        for (int i = 1; i <= remaining; i++) {
	        ans[i]++;
        }

        return ans;
    }
}
Python
class Solution:
    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:
        m = len(rolls)
        # Calculate the total sum needed for the n + m rolls to have the given mean
        total_sum = mean * (n + m)
        # Calculate the current sum of the observed rolls
        current_sum = sum(rolls)
        # Calculate the sum needed from the missing n rolls
        missing_sum = total_sum - current_sum

        # Check if it is possible to split missing_sum into n parts with each part between 1 and 6
        if missing_sum < n or missing_sum > 6 * n:
            return []

        # Construct the result
        res = [1] * n
        missing_sum -= n  # We have initially assigned each part as 1

        for i in range(n):
            if missing_sum > 0:
                add = min(
                    5, missing_sum
                )  # We can add at most 5 more to each part
                res[i] += add
                missing_sum -= add

        return res

Complexity

  • ⏰ Time complexity: O(m + n)
    • O(m) for summing m rolls and
    • O(n) for getting values for n rolls
  • 🧺 Space complexity: O(n) for storing answer