Leet Code POTD – 2028. Find Missing Observations | in JS

Problem Statement:

You are given an integer array rolls that represents the result of rolling a dice n times, and two integers mean and n. You need to roll the dice m more times, and you need to find the missing observations for these m rolls such that the average of the n + m rolls equals the mean.

The dice is a standard 6-sided die, which means the possible outcomes are 1 through 6.

Approach:

1. Calculate the target sum:
   The target sum of all n + m dice rolls should be mean * (n + m).
2. Calculate the sum of the given rolls:
   We can find the sum of the given n rolls by summing up all the elements of the rolls array.
3. Find the required sum for the missing rolls:
   Subtract the sum of the given rolls from the target sum to find how much the sum of the m missing rolls should be.
4. Check for feasibility:
   Each dice roll must be between 1 and 6. Therefore, the sum of the missing rolls should be between m * 1 (the minimum possible sum) and m * 6 (the maximum possible sum). If the required sum is outside this range, it’s not possible to achieve the goal, and we return an empty array.
5. Distribute the required sum:
   Once the sum is found to be feasible, we can distribute it among the m missing rolls. Start by assigning each roll the minimum value of 1, and then distribute the remaining sum across the rolls in a balanced way, ensuring no roll exceeds 6.

JavaScript Implementation:

/**
 * @param {number[]} rolls
 * @param {number} mean
 * @param {number} n
 * @param {number} m
 * @return {number[]}
 */
var missingRolls = function(rolls, mean, m) {
    // Step 1: Calculate the target sum
    let totalSum = (rolls.length + m) * mean;

    // Step 2: Calculate the sum of the given rolls
    let currentSum = rolls.reduce((a, b) => a + b, 0);

    // Step 3: Calculate the sum required for the missing rolls
    let missingSum = totalSum - currentSum;

    // Step 4: Check if it's possible to distribute the missing sum across m rolls
    if (missingSum < m || missingSum > m * 6) {
        return [];
    }

    // Step 5: Distribute the missing sum across the m rolls
    let result = new Array(m).fill(1);
    missingSum -= m; // We have already assigned 1 to each roll

    for (let i = 0; i < m && missingSum > 0; i++) {
        let add = Math.min(5, missingSum); // The maximum we can add is 5
        result[i] += add;
        missingSum -= add;
    }

    return result;
};

// Example usage:
console.log(missingRolls([3, 2, 4, 3], 4, 4)); // Output: [6, 6, 5, 5]

Explanation:

1. totalSum: The target total sum for n + m rolls is calculated as (n + m) * mean.
2. currentSum: We compute the sum of the already known n rolls by summing up all the values in rolls.
3. missingSum: The sum required for the m missing rolls is the difference between totalSum and currentSum.
4. Feasibility check: If missingSum is less than m (each roll must be at least 1) or greater than m * 6 (each roll must be at most 6), it is impossible to generate the required missing rolls, so we return an empty array.
5. Distribute the missing sum: We start by assigning each of the m missing rolls a value of 1. Then, we distribute the remaining sum by adding as much as possible (up to 5) to each roll without exceeding 6.

Time Complexity:

• O(m): We iterate over the m missing rolls to distribute the missing sum.

Space Complexity:

• O(m): We use an array to store the result of the m missing rolls.