Find Missing Observations solution and explanation
Google
9 more videos on this problem
Find Missing Observations - Leetcode 2028 Weekly Contest Problem - PythonNeetCode · 13:08 · 10K views
Find Missing Observations - Leetcode 2028 - PythonNeetCodeIO · 11:24 · 7K views
LeetCode Daily: Find Missing Observations Solution in Java | September 5, 2024AlgoXploration · 0:46 · 475 views
Find Missing Observations (LeetCode 2028) (Array, Maths)CodeWithARB · 15:45 · 407 views
2028. Find Missing Observations (Leetcode Medium)Programming Live with Larry · 9:01 · 385 views
LeetCode 2028 - Find Missing Observations - JavaAlpha-Code · 13:57 · 189 views
2028. Find Missing ObservationsLeetcode and Interview Question · 13:05 · 128 views
Find Missing Observations | LeetCode 2028 | Beginners Easy ApproachCodeInBits · 15:21 · 89 views
2028. Find Missing Observations | Array | Logic | Math | LeetCode | MediumLeet's Code · 27:42 · 78 views
Leetcode 2028: Find Missing ObservationsThe algorithm Architect · 6:19 · 63 views
The 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.
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.length1 <= n, m <= 1051 <= rolls[i], mean <= 6
Approach overview
Problem Overview: You are given several observed dice rolls and the overall mean of all rolls (observed + missing). Each roll is between 1 and 6. The task is to reconstruct the n missing rolls so the final average matches the given mean. If it is impossible to form valid dice values, return an empty array.
Approach 1: Calculate Missing Sum and Distribute Among Rolls (Time: O(m + n), Space: O(n))
This approach relies on simple math and array operations. First compute the total sum required for all rolls using mean * (m + n), where m is the number of observed rolls. Subtract the sum of the observed array to get the total value the missing rolls must contribute. If this value is outside the feasible range [n, 6n], there is no valid solution because dice values must stay between 1 and 6.
Once the required sum is valid, distribute it across n elements. Start by assigning the base value missingSum // n to each position and distribute the remainder by incrementing elements by one until the total matches the required sum. This guarantees all values remain within bounds while keeping the distribution balanced. The algorithm performs a single pass over the input and builds the result array directly.
Approach 2: Iterative Construction of Missing Rolls (Time: O(m + n), Space: O(n))
This method builds the missing sequence step by step using a greedy simulation. Compute the total missing sum the same way as the previous approach. Instead of evenly distributing values immediately, iterate through the n positions and assign a value that keeps the remaining sum feasible for the remaining slots.
At each step, choose the smallest valid value that still allows the remaining positions to stay within the dice bounds. For example, if you place x, ensure the remaining sum can still fall within [remainingSlots, 6 * remainingSlots]. This constraint check guarantees that future assignments remain valid. The process continues until all n values are assigned or the constraints fail.
This approach is useful when you want explicit control over each assignment or when explaining feasibility constraints during interviews. It makes the reasoning about bounds very clear, though it performs the same number of operations as the direct distribution method.
Recommended for interviews: The missing sum distribution approach is the most common solution because it reduces the problem to a straightforward arithmetic constraint and balanced allocation. Interviewers expect you to first verify the feasibility range [n, 6n] and then construct the result in linear time. Demonstrating the iterative feasibility check also shows strong reasoning about constraints and edge cases.
Approach 1: Calculate Missing Sum and Distribute Among Rolls
First, calculate the total required sum for n + m rolls to satisfy the given mean. Then, compute the sum of the already available rolls and determine how much more is needed from the n missing rolls. If the required sum for the missing rolls is feasible (i.e., between n and 6*n), distribute the required sum across the missing rolls aiming for an even distribution.
def missingRolls(rolls, mean, n):
m = len(rolls)
total_sum = mean * (n + m)
current_sum = sum(rolls)
missing_sum = total_sum - current_sum
if missing_sum < n or missing_sum > 6 * n:
return []
base = missing_sum // n
remainder = missing_sum % n
result = [base + 1] * remainder + [base] * (n - remainder)
return resultimport java.util.*;
public class Solution {
public int[] missingRolls(int[] rolls, int mean, int n) {
int m = rolls.length;
int totalSum = mean * (n + m);
int currentSum = 0;
for (int roll : rolls) {
currentSum += roll;
}
int missingSum = totalSum - currentSum;
if (missingSum < n || missingSum > 6 * n) {
return new int[0];
}
int base = missingSum / n;
int remainder = missingSum % n;
int[] result = new int[n];
for (int i = 0; i < n; i++) {
result[i] = (i < remainder) ? base + 1 : base;
}
return result;
}
}In this Python solution, we first calculate the total_sum that is needed by multiplying mean with n + m. We then subtract the current_sum of the known rolls from total_sum to find missing_sum, which represents the sum needed from the missing rolls. If missing_sum is not feasible (not between n and 6 * n), we return an empty array. Otherwise, we distribute the missing_sum into parts to create the missing rolls.
The time complexity is O(n + m), where n and m are the number of missing and known observations, respectively, due to the sum calculations and array operations. The space complexity is O(n), for the storage of the missing rolls.
Approach 2: Iterative Construction of Missing Rolls
This approach iteratively builds the missing rolls by ensuring each additional roll keeps the total sum within possible bounds. Start with an empty list for the missing rolls, and iteratively add values ensuring the sum remains feasible, adjusting at each step.
#include <vector>
using namespace std;
vector<int> missingRolls(vector<int>& rolls, int mean, int n) {
int m = rolls.size();
int totalSum = mean * (n + m);
int currentSum = accumulate(rolls.begin(), rolls.end(), 0);
int missingSum = totalSum - currentSum;
if (missingSum < n || missingSum > 6 * n) return {};
vector<int> result(n, 1);
missingSum -= n;
for (int i = 0; i < n && missingSum > 0; ++i) {
int add = min(missingSum, 5);
result[i] += add;
missingSum -= add;
}
return result;
}function missingRolls(rolls, mean, n) {
let m = rolls.length;
let totalSum = mean * (n + m);
let currentSum = rolls.reduce((a, b) => a + b, 0);
let missingSum = totalSum - currentSum;
if (missingSum < n || missingSum > 6 * n) return [];
let result = new Array(n).fill(1);
missingSum -= n;
for (let i = 0; i < n && missingSum > 0; i++) {
let add = Math.min(missingSum, 5);
result[i] += add;
missingSum -= add;
}
return result;
}In this C++ solution, we accumulate the currentSum using std::accumulate. If the calculated missingSum is valid, we initialize a result vector with all ones. We then iteratively increase each entry by a maximum possible value (up to 5, since each die can have a maximum value of 6) until the missing sum is fulfilled.
The time complexity is O(n + m) due to the sum calculation and iteration over the missing rolls. The space complexity is O(n) for the missing rolls' storage.
Approach 3: Construction
According to the problem description, the sum of all numbers is (n + m) times mean, and the sum of known numbers is sum_{i=0}^{m-1} rolls[i]. Therefore, the sum of the missing numbers is s = (n + m) times mean - sum_{i=0}^{m-1} 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).
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;
}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
}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
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Calculate Missing Sum and Distribute Among Rolls | The time complexity is O(n + m), where n and m are the number of missing and known observations, respectively, due to the sum calculations and array operations. The space complexity is O(n), for the storage of the missing rolls. |
| Iterative Construction of Missing Rolls | The time complexity is O(n + m) due to the sum calculation and iteration over the missing rolls. The space complexity is O(n) for the missing rolls' storage. |
| Construction | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Calculate Missing Sum and Distribute | O(m + n) | O(n) | General case. Clean mathematical solution with minimal logic. |
| Iterative Construction of Missing Rolls | O(m + n) | O(n) | When explaining feasibility constraints step-by-step or simulating assignments. |
Frequently asked questions
Is Find Missing Observations easy or hard?
Find Missing Observations is rated Medium difficulty on LeetCode with an acceptance rate around 57%. The implementation is straightforward once you identify the missing sum constraint, but recognizing the feasibility range [n, 6n] is the key insight.
Find Missing Observations Python/Java solution
A typical Python or Java solution computes the required missing sum, checks if it lies within [n, 6n], then fills an array with base value missingSum // n and distributes the remainder across elements. Both implementations run in O(m + n) time and use O(n) extra space.
How to solve Find Missing Observations in O(n)?
First compute the required total sum from the given mean. Subtract the sum of known rolls to get the missing sum. If the value is outside [n, 6n], return an empty array. Otherwise distribute the sum across n elements using integer division and remainder handling, which builds the result in linear time.
What is the best approach for Find Missing Observations?
The most efficient approach computes the total required sum using mean * (m + n), subtracts the sum of observed rolls, and distributes the remaining value across the missing rolls. A feasibility check ensures the sum lies within [n, 6n]. This solution runs in O(m + n) time and O(n) space.
Is Find Missing Observations asked at Google/Amazon/Meta?
This problem represents a typical interview pattern involving arithmetic constraints and array construction. Variants of this question appear in coding interviews at large tech companies because they test reasoning about bounds, feasibility checks, and linear-time array construction.
What data structure is used in Find Missing Observations?
The problem primarily uses arrays along with simple mathematical calculations. No advanced data structures are required. The key idea is computing sums and constructing an array that satisfies the constraints of dice values between 1 and 6.
What is the time complexity of Find Missing Observations?
The optimal solution runs in O(m + n) time, where m is the number of observed rolls and n is the number of missing rolls. You compute the observed sum once and construct the result array once. Space complexity is O(n) because you return the missing rolls array.