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 i^th 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.

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 <= 10⁵
1 <= rolls[i], mean <= 6

Solutions

Solution 1: Construction

According to the problem description, the sum of all numbers is \((n + m) \times \textit{mean}\), and the sum of known numbers is \(\sum_{i=0}^{m-1} \textit{rolls}[i]\). Therefore, the sum of the missing numbers is \(s = (n + m) \times \textit{mean} - \sum_{i=0}^{m-1} \textit{rolls}[i]\).

If \(s \gt n \times 6\) or \(s \lt n\), it means there is no answer that satisfies the conditions, so we return an empty array.

Otherwise, we can evenly distribute \(s\) to \(n\) numbers, that is, the value of each number is \(s / n\), and the value of \(s \bmod n\) numbers is increased by \(1\).

The time complexity is \(O(n + m)\), where \(n\) and \(m\) are the number of missing numbers and known numbers, respectively. Ignoring the space consumption of the answer, the space complexity is \(O(1)\).

Python3JavaC++GoTypeScriptRust

class Solution:
    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:
        m = len(rolls)
        s = (n + m) * mean - sum(rolls)
        if s > n * 6 or s < n:
            return []
        ans = [s // n] * n
        for i in range(s % n):
            ans[i] += 1
        return ans

class Solution {
    public int[] missingRolls(int[] rolls, int mean, int n) {
        int m = rolls.length;
        int s = (n + m) * mean;
        for (int v : rolls) {
            s -= v;
        }
        if (s > n * 6 || s < n) {
            return new int[0];
        }
        int[] ans = new int[n];
        Arrays.fill(ans, s / n);
        for (int i = 0; i < s % n; ++i) {
            ++ans[i];
        }
        return ans;
    }
}

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

func missingRolls(rolls []int, mean int, n int) []int {
    m := len(rolls)
    s := (n + m) * mean
    for _, v := range rolls {
        s -= v
    }
    if s > n*6 || s < n {
        return []int{}
    }
    ans := make([]int, n)
    for i, j := 0, 0; i < n; i, j = i+1, j+1 {
        ans[i] = s / n
        if j < s%n {
            ans[i]++
        }
    }
    return ans
}

function missingRolls(rolls: number[], mean: number, n: number): number[] {
    const m = rolls.length;
    const s = (n + m) * mean - rolls.reduce((a, b) => a + b, 0);
    if (s > n * 6 || s < n) {
        return [];
    }
    const ans: number[] = Array(n).fill((s / n) | 0);
    for (let i = 0; i < s % n; ++i) {
        ans[i]++;
    }
    return ans;
}

impl Solution {
    pub fn missing_rolls(rolls: Vec<i32>, mean: i32, n: i32) -> Vec<i32> {
        let m = rolls.len() as i32;
        let s = (n + m) * mean - rolls.iter().sum::<i32>();

        if s > n * 6 || s < n {
            return vec![];
        }

        let mut ans = vec![s / n; n as usize];
        for i in 0..(s % n) as usize {
            ans[i] += 1;
        }

        ans
    }
}

2028. Find Missing Observations

Description

Solutions

Solution 1: Construction

Comments