2028. Find Missing Observations

Description

The problem is to find an array of missing dice rolls that, when combined with a given array of observed dice rolls, results in an overall mean equal to a specified value. The challenge is to ensure that the total of the missing rolls satisfies the properties of dice (i.e., each value must be between 1 and 6) while achieving the desired overall sum.

Given the observed rolls, the mean, and the number of missing rolls, the task is to calculate the missing rolls such that the average of all the rolls (both observed and missing) matches the given mean.

Intuition

The key insight is that the sum of all rolls (observed and missing) must match the total sum implied by the mean. The sum of the missing rolls must fit within a valid range for dice values. Once the total required sum for the missing rolls is computed, the missing values can be distributed evenly, with any remainder distributed to adjust the values while staying within the range [1, 6].

We check if the sum of missing values can be distributed among the missing rolls. If it can, we distribute the base values and allocate any remainder by incrementing a few values.

Approach

1. Calculate Total Sum: - Compute the total sum required for all rolls using the formula mean * (n + m) where n is the number of missing rolls, m is the number of observed rolls, and mean is the desired overall mean.
2. Calculate Missing Sum: - Calculate the sum of the observed rolls. - Subtract the observed sum from the total sum to get the sum required for the missing rolls.
3. Check Validity: - Ensure that the missing sum is between n (the smallest possible sum for missing rolls) and 6 * n (the largest possible sum).
4. Distribute Values: - If the missing sum is valid, distribute the sum as evenly as possible across the missing rolls. This can be done by assigning a base value to all rolls and then distributing the remainder by incrementing some rolls.
5. Return Result: - If a valid solution exists, return the result; otherwise, return an empty array.

Complexity

Time Complexity:

• Calculating the sum of the observed rolls takes (O(m)), where (m) is the length of the rolls array.
• Distributing the base value and remainder takes (O(n)), where (n) is the number of missing rolls.
• Overall time complexity is (O(m + n)).

Space Complexity:

• The space complexity is (O(n)), where (n) is the number of missing rolls, due to the storage of the result array.

Code

C++

class Solution {
public:
    std::vector missingRolls(std::vector& rolls, int mean, int n) {
        int m = rolls.size();
        int totalSum = mean * (n + m);
        int observedSum = std::accumulate(rolls.begin(), rolls.end(), 0);
        int missingSum = totalSum - observedSum;

        if (missingSum < n || missingSum > 6 * n) {
            return {};
        }

        int base = missingSum / n;
        int remainder = missingSum % n;

        std::vector result(n, base);
        for (int i = 0; i < remainder; ++i) {
            result[i] += 1;
        }
        return result;
    }
};

Python

class Solution:
    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:
        m = len(rolls)
        total_sum = mean * (n + m)
        observed_sum = sum(rolls)
        missing_sum = total_sum - observed_sum

        if missing_sum < n or missing_sum > 6 * n:
            return []

        base = missing_sum // n
        remainder = missing_sum % n

        result = [base] * n
        for i in range(remainder):
            result[i] += 1

        return result

Java

class Solution {
    public int[] missingRolls(int[] rolls, int mean, int n) {
        int m = rolls.length;
        int totalSum = mean * (n + m);
        int observedSum = Arrays.stream(rolls).sum();
        int missingSum = totalSum - observedSum;

        if (missingSum < n || missingSum > 6 * n) {
            return new int[0];
        }

        int base = missingSum / n;
        int remainder = missingSum % n;

        int[] result = new int[n];
        Arrays.fill(result, base);

        for (int i = 0; i < remainder; i++) {
            result[i] += 1;
        }

        return result;
    }
}

JavaScript

/**
 * @param {number[]} rolls
 * @param {number} mean
 * @param {number} n
 * @return {number[]}
 */
var missingRolls = function (rolls, mean, n) {

    let m = rolls.length;
    let totalSum = mean * (n + m);
    let observedSum = rolls.reduce((a, b) => a + b, 0);

    let missingSum = totalSum - observedSum;

    if (missingSum < n || missingSum > 6 * n) {
        return [];
    }

    let base = Math.floor(missingSum / n);
    let remainder = missingSum % n;

    let result = new Array(n).fill(base);
    for (let i = 0; i < remainder; i++) {
        result[i] += 1;
    }
    return result;
};