2028. Find Missing Observations

Description

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

 

Solutions

Solution: Simulation

• Time complexity: O(m+n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} rolls
 * @param {number} mean
 * @param {number} n
 * @return {number[]}
 */
const missingRolls = function (rolls, mean, n) {
  const MAX_ROLL = 6;
  const size = rolls.length + n;
  const total = size * mean;
  const missingObservations = total - rolls.reduce((sum, value) => sum + value);
  const average = Math.floor(missingObservations / n);
  const eachMax = MAX_ROLL - average;
  let remain = missingObservations - average * n;

  if (average > MAX_ROLL || average <= 0) return [];
  if (eachMax === 0 && remain) return [];
  const result = new Array(n).fill(average);
  let index = 0;

  while (remain) {
    const missing = Math.min(remain, eachMax);

    remain -= missing;
    result[index] += missing;
    index += 1;
  }
  return result;
};